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!
Antworten:
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:
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.
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.
quelle
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.)
quelle