Warum heißt eine reguläre Sprache "regulär"?

31

Ich habe gerade das erste Kapitel der Einführung in die Berechnungstheorie von Michael Sipser abgeschlossen, in dem die Grundlagen endlicher Automaten erklärt werden.

Er definiert eine reguläre Sprache als alles, was durch endliche Automaten beschrieben werden kann. Aber ich konnte nicht finden, wo er erklärt, warum eine reguläre Sprache "regulär" heißt? Woher kommt in diesem Zusammenhang der Begriff "regelmäßig"?

HINWEIS: Ich bin ein Anfänger, bitte versuchen Sie es in einfachen Worten zu erklären!

Phil Wright
quelle
6
Es scheint , dass diese zurück geht zu Kleene und sein Studium der regulären Sets .
Kaveh

Antworten:

28

Wie Kaveh in einem Kommentar sagt, verlieh Kleene den Namen schon vor langer Zeit, als er die Automatentheorie und die formalen Sprachen einführte. Ich glaube, der Begriff war willkürlich, obwohl es viele Jahre her ist, seit ich seine Originalarbeit gelesen habe.

Mathematiker haben die Angewohnheit, gebräuchliche Substantive und Adjektive für mathematische Objekte und Eigenschaften zu missbrauchen, manchmal mit guten Gründen wie geometrischen oder anderen Analogien oder Metaphern und manchmal willkürlich. Betrachten Sie einfach "Gruppe", "Ring", "Raum", "Garbe", "Atlas", "Mannigfaltigkeit", "Feld" und so weiter.

Tatsächlich wird der Begriff "regulär" für Sprachen mit endlichen Zuständen, obwohl er in der Automatentheorie immer noch weit verbreitet ist, in der algebraischen Cousine, der Theorie der endlichen Halbgruppen oder der abstrakten Algebra im Allgemeinen nicht sehr häufig verwendet. Warum? Da der Begriff bereits für eine Halbgruppe verwendet wurde, die in einem bestimmten technischen Sinne einer Gruppe nahe steht, konnte eine reguläre Sprache im Sinne von Kleene nicht mit einer entsprechenden regulären Halbgruppe verglichen werden . Drittens definierte Kleene eine andere Art von Ereignis mit dem Namen "definitiv", das eine Zeitlang intensiv untersucht wurde, sich jedoch als nicht besonders fruchtbar herausstellte. Endliche Sprachmengen spielen heute die Rolle bestimmter Ereignisse als Grundlage für regelmäßige Ereignisse.

Der bevorzugte Begriff in der Algebra ist "rational" sowohl für Kleenes Sprachklasse als auch für die allgemeineren Halbgruppen und Monoiden. Diese Verwendung spiegelt auch eine wichtige Analogie zwischen dem Begriff "rational" in der Algebra als Lösung einer linearen Gleichung mit ganzzahligen Koeffizienten und dem Konzept rationaler Potenzreihen in der Automatentheorie und der formalen Sprachtheorie wider.


Zusätzliche Information. Kleenes Originalarbeit von 1951 mit dem Titel "Darstellung von Ereignissen in Nervennetzen und endlichen Automaten" ist hier zu finden . Auf P. 46 es regelt die Willkür des Begriffs "regelmäßig" mit dieser Aussage:

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.)

Anscheinend hat sich niemand einen aussagekräftigeren Begriff ausgedacht. ;-)

Wie so oft bei wegweisenden Arbeiten, die zu einer intensiven Erschließung ganz neuer Bereiche führen, sind Terminologie und Konzepte heutzutage kaum mehr wiederzuerkennen. Zunächst ging es um Modelle von Neuronen, daher die Verwendung von "Ereignissen" anstelle von "Sprachen" oder "Mengen". Der Begriff "Ereignisse" hielt bis in die 60er und 70er Jahre an, obwohl Kleenes Konzepte für Automaten und formale Sprachen den Wert für die Neurowissenschaften bei weitem überwogen.

einbeinein+dass wir heute verwenden. Kleenes Motivation war es, die leere Zeichenkette (oder ein Ereignis mit der Dauer Null in seinen Begriffen) zu vermeiden. Das war eine bemerkenswert vorausschauende Intuition, da die nachfolgende Theorie gezeigt hat, wie wichtig es ist, die leere Zeichenkette in vielen Zusammenhängen in die Definitionen einzuschließen oder auszuschließen. Drittens hat Kleene ein Konzept definiert, das "bestimmte Ereignisse" genannt wird, und daraus regelmäßige Ereignisse entwickelt, aber heutzutage verwenden wir zu diesem Zweck endliche Mengen. Bestimmte Ereignisse wurden für eine Weile untersucht, haben sich jedoch als weit weniger wichtig als reguläre Ereignisse / Sets / Sprachen herausgestellt.

Wie auch immer, eine vollständige Lektüre dieses Papiers ist heute wahrscheinlich niemandes Zeit wert, außer aus historischen Gründen. Ich habe es nur nach den entscheidenden Definitionen und Ideen durchsucht, und das hat Spaß gemacht.

David Lewis
quelle
6
"Regular" ist stark überlastet und es gibt nicht-rationale Sprachen mit rationalen Erzeugungsfunktionen. Beide Begriffe sind zum Kotzen.
Raphael
2
Vielen Dank, dass Sie Kleenes wegweisendes Papier ausgraben. Ich würde sagen, dass wir, wenn Automaten als Rechenmodelle verwendet werden , im Gegensatz zu Spracherkennern, immer noch den Begriff "Ereignisse" für die Eingabe- / Ausgabesymbole verwenden. Aber Kleenes Artikel ist aus einem anderen Grund immer noch lesenswert. In der Informatik sollte auch untersucht werden, wie Berechnungen in der natürlichen und der sozialen Welt ablaufen. Außerdem sollte untersucht werden, wie sie in unseren eigenen Maschinen ablaufen. Wir haben diesen Fokus im Laufe der Jahre verloren, weil wir vom unaufhaltsamen Fortschritt der Technologie verzehrt werden.
Uday Reddy
1
Die Veröffentlichung wurde erst 1956 in einem AMS-Band mit dem Titel Automata Studies veröffentlicht, der mehrere wichtige frühe Veröffentlichungen in der Automatentheorie enthielt. Ah, die wundervollen Tage vor dem Web und dem sofortigen Veröffentlichen - als sich die Dinge viel langsamer bewegten. Sie können das Buch bei Amazon für nur 72,50 USD oder für 12 USD + Versand erwerben .
David Lewis
4

Ich habe den Begriff "regelmäßig" immer so verstanden, dass er auf einem sich wiederholenden Muster basiert. Nachdem Sie alle Zeichenfolgen einer bestimmten Länge aufgelistet haben, haben Sie sie alle gesehen. Danach wird es nichts Neues geben.

(Es ist natürlich nur eine vage Intuition.)

Uday Reddy
quelle