Warum heißen reguläre Sprachen "regulär"?

27

Warum werden reguläre Sprachen (und von diesen regulären Ausdrücken) "regulär" genannt? Es gibt viel Regelmäßigkeit auch in kontextfreien Sprachen anderer Arten von Sprachen.

Ich nehme an, dass am Anfang das Adjektiv "regulär" verwendet wurde, um diese Art von Sprachen von anderen "nicht regulären" oder irgendwie anormalen Sprachen zu unterscheiden. Wenn ja, wo waren diese anderen Typen und was war ihre Unregelmäßigkeit ?

regular-expressions regular-language ho.history-overview gioele
quelle
1
kein besserer Grund als der Grund, warum normale Untergruppen "normal" genannt werden?
Sasho Nikolov
2
@SashoNikolov: math.stackexchange.com/questions/898977/…
Joshua Grochow

Antworten:

39

Eine schnelle Überprüfung der Quellen zeigt, dass Chomsky die Ebenen seiner Hierarchie nur als "Typ 0, Typ 1, Typ 2, Typ 3" bezeichnet hat. In einer Fußnote erwähnt er, dass sein Typ 3 „regelmäßigen Ereignissen“ von Kleene entspricht . Kleene schrieb dort: " Wir werden jetzt eine Klasse von Ereignissen beschreiben, die wir" regelmäßige Ereignisse "nennen werden." (Wir würden uns über Vorschläge zu einem aussagekräftigeren Begriff freuen.)

Es scheint also, dass der Begriff ein historischer Unfall ist und in keinem Fall Einfluss auf das Verhältnis regulärer Sprachen zu kontextfreien Sprachen hat.

Emil Jeřábek unterstützt Monica
quelle
6
Das Papier der Kleene (ein großartiges Papier, danke!) Vergleicht "regelmäßige" Ereignisse mit "unbestimmten" Ereignissen (die von einem anderen Ereignis abhängen, das möglicherweise in einer unendlichen Vergangenheit stattgefunden hat) und "bestimmten" Ereignissen (die von höchstens bestimmten Ereignissen abhängen vergangene Momente). "Regelmäßige" Ereignisse sind Ereignisse, die vom "Wert" des letzten Moments abhängen . p−l−1p
Gioele
9
Das Papier zeigt auch, dass wir Kleen danken müssen, wenn reguläre Sprachen "regulär" und nicht "nachvollziehbar" heißen.
Gioele