Diskussion:Satz von Myhill-Nerode

Diskussion um $\sim$

Den Bezeichner $\sim ^{L}$ für die Relation finde ich beim Lesen recht störend. Wie wäre es, statt dessen $R_{L}$ oder $\equiv _{L}$ zu wählen?

Allerdings wäre Konsistenz sicher wichtiger, ich habe keinen Überblick über die verwandten Artikel.

--136.199.8.128 17:41, 29. Jun 2005 (CEST)

$\sim$ ist meiner Erfahrung nach das üblichste Symbol für Äquivalenzrelationen und wird auch im Artikel Äquivalenzrelation benutzt. Ich weiß nicht, warum er schwerer lesbar sein soll als z.B. $\equiv$. Ich bin daher für die Beibehaltung von $\sim$. Man könnte den Index L nach unten schreiben - dann wird es vielleicht besser lesbar? --Taniquetil 22:40, 29. Jun 2005 (CEST)

Nach wem ist der Satz benannt? Anders gefragt: Wer war / ist Myhill-Nerode? -- tsor 22:45, 29. Jun 2005 (CEST)

---

Gut, bleiben wir bei $\sim$.

Anil Nerode hat 1958 seinen Artikel zu dem Thema veröffentlicht seine Homepage gibt als Beschäftigung bis 1957 an: "Institute for Air Weapons Research, Chicago, Illinois". J. Myhills Aufsatz ist 1957 in einer Zeitschrift der US Air Force erschienen. Das ist wohl nicht genug für eigene Artikel über die beiden.

Die Quellen, ungeprüft: A. Nerode: Linear automaton transformations. Proceedings of the American Mathematical Society 9 (1958) pp. 541-544. J. Myhill: Finite automata and the representation of events. WADD TR-57-624 (1957), pp. 112-137

--136.199.8.128 12:50, 30. Jun 2005 (CEST)

Beispiel unklar. :-(

Ich kapiere das Beispiel irgendwie nicht.

Wenn $L=\{a^{n}b^{n}|n\geq 1\}$ ist, dann enthält $L$ die Wörter $ab,aabb,aaabbb,aaaabbbb,...$ weil stets gleich viele $a$'s und $b$'s in einem Wort enthalten sein sollen. Somit sind Wörter wie $aab,aaab,aaaab,...$ doch gar nicht in $L$. Was sollen die dann in dem Beweis?

--RokerHRO 15:11, 2. Sep 2005 (CEST)

Das Beispiel hat in dieser Hinsicht schon recht gehabt. aab, aaab, aaaab sind zwar keine Wörter aus L, aber sie sind Präfixe von Wörtern aus L, das heißt es gibt Buchstabenkombinationen (= Suffixe), mit denen sie zu Wörtern aus L ergänzt werden können – und das ist es, was zählt. Aber das Beispiel hatte einige andere Haker. Ich habe es zusammen mit vielen anderen inhaltlichen Fehlern korrigiert. --Thetawave 14:21, 17. Dez 2005 (CET)

Nein, Thetawave! Die Äquivalenzklassen bzgl. der Nerode-Relation werden von den SUFFixen bestimmt. In einer Aquivalenzklasse liegen Wörter, welche durch das gleiche Suffix zu Wörtern in L werden. Das Beispiel für die nichtreguläre Sprache vom 17.12. war richtig! Du hast die Äquivalenzklassen nach Präfix gebildet. Also bitte wieder herstellen. -- 141.35.13.48 23:18, 17. Jan 2006 (CET)

Du hast recht, ich habe hier zwei Herangehensweisen vermischt: Der Index entspricht sowohl der Anzahl der Äquivalenzklassen, als auch der Anzahl der Suffixsprachen. Ich habe mit den Äquivalenzklassen angefangen, aber dann mit den Suffixsprachen weitergemacht. Ich werde das korrigieren. Das kommt davon, wenn man mit mehreren Quellen gleichzeitig arbeitet :-( --Θ~ 20:17, 20. Jan 2006 (CET)

Fehler korrigiert

Das Beispiel $L:=\{a^{n}b^{n}|n\in \mathbb {N} \}$ war nicht ganz korrekt. In der korrigierten Ausgabe von 2003 des Buches "Theoretische Informatik kurz gefasst" von Schöning wurde der Fehler auch beseitigt. Es geht darum, das jeweils am Anfang der Äquivalenzklassen $a$,$a^{2}$ usw. auftauchte. Aber (betrachten wir einmal die erste Klasse der ursprünglichen Version) $a$ z.B. ist nicht äquivalent zu z.B.$a^{2}b$, da als Suffix nicht nur $b$, sondern z.B. auch $ab^{2}$ (eigentlich jedes Wort über der Sprache über dem Eingabealphabet $\Sigma$) eingesetzt werden kann. In diesem Falle würde dann das eine so entstandene Wort $aab^{2}$ zur Sprache gehören, das andere Wort $a^{2}bab^{2}$ aber nicht. Das widerspräche der vorliegenden Äquivalenzrelation. Benutzer:AnnaAda 20:58, 27. Mai 2007

Beispiel: Wörter endlicher Länge?

Laut http://de.wikipedia.org/wiki/Wort%20(Theoretische%20Informatik) haben Wörter immer endliche Länge. Insofern ist die Betonung der Endlichkeit der Wörter im 1. Beispiel redundant, ich würde sogar sagen verwirrend. Darum mein Vorschlag für die Überschrift: "Alle Sprachen mit endlich vielen Wörtern sind regulär" oder noch lieber: "Jede endliche Sprache ist regulär". Im Text wäre entsprechend auch noch einiges zu ändern. Gibt's da Einwände? --130.149.17.40 15:50, 12. Jun. 2007 (CEST)

Beweis des Satzes an sich?

Hallo, man sollte noch einen Beweis des Satzes an sich einfügen. --134.155.8.81 13:26, 14. Jan. 2008 (CET)

Beschreibung des 2. Bildes

Die Begründung, die unter dem 2. Bild steht, wieso es keinen endlichen Automat gibt, der die Sprache L := {ab, aabb, aaabbb, ...} akzeptieren kann, ist meiner Meinung nach Irreführend. Da alle Endzustände äquivalent sind (alle ausgehenden Kanten sind gleich), könnte man diese zusammenfassen. Somit hätte der Automat eine endliche Anzahl an Endzuständen (1). Die Begründung ("Jedes der unendlich vielen Wörter aus L benötigt einen eigenen Endzustand") ist somit falsch. Die Grundaussage ist jedoch richtig.

Stimmt genau. Muss geändert werden. --Benji 23:50, 4. Mai 2010 (CEST)

Übertrag

Hallo,

sorry ich bin und werde voraussichtlich auch kein aktiver Wikipedia-Editor. Vielleicht ist aber jemand unter den Aktiven so nett und bringt die von mir unten angesprochene Korrektur an?

Es geht um den Artikel "Satz von Myhill-Nerode":

Beim zweiten Bild steht "Jedes der unendlich vielen Wörter aus L benötigt einen eigenen Endzustand, der Automat hat also unendliche Größe." Letzteres stimmt zwar, aber ersteres als Begründung ist falsch.

Im Skriptteil http://private.sit.fhg.de/%7Ebaumgart/PNFolSkr/SkriptWS0809am081014%2001_08.pdf findet sich auf S.8 ein unendlicher Automat für die gleiche Sprache mit nur zwei Endzuständen. Der tatsächliche Grund für die Unendlichkeit jedes Automaten für anbn liegt in der Unendlichkeit der Restsprachen, deren jede (mindestens) einen Zustand erfordert. Das Bild im Skript zeigt übrigens sogar "den minimalen unendlichen Automaten" - jede Restsprache entspricht einem Zustand und nicht mehreren.

Viele Grüße Bernd [1] Übertrag eines verirrten Beitrags --He3nry Disk. 10:43, 13. Apr. 2011 (CEST)

Damit man das Bild nicht neu zeichnen muss, habe ich nur die Beschreibung geändert. --Zahnradzacken 22:20, 30. Mai 2011 (CEST)

Bild zu $L=\{a^{*}\}$

"Ein minimaler Deterministischer endlicher Automat, der die Sprache a* akzeptiert." Meiner Meinung nach fehlt da der Startzeiger, sprich ein minimaler Automat muss einen Startzustand haben. --77.0.14.95 17:49, 30. Mai 2011 (CEST)

Habe das Bild durch eine Version mit solch einem Pfeil ersetzt, bei der Gelegenheit gleich durch eine Vektorgrafik. --Zahnradzacken 22:20, 30. Mai 2011 (CEST)

Satz ist umfangreicher

Laut Erk/Priese besagt der Satz von Myhill-Nerode zusätzlich, dass eine dritte Aussage äquivalent zu L ist regulär (eigtl.: L ist rational) ist:

$L$ ist die Vereinigung einiger Äquivalenzklassen einer Kongruenz von endlichem Index über $\Sigma ^{*}$.

Ich finde das zwar nicht so exorbitant wichtig, aber vielleicht sollte es doch in den Artikel? Was meint Ihr? -- UKoch 13:57, 13. Dez. 2011 (CET)

Satz von Myhill und Nerode

Wieso "Satz von Myhill-Nerode"? Es handelt sich doch um zwei Personen mit separaten Nachnamen, nicht um eine Person mit Doppelnamen.

siehe:

"Satz von Myhill und Nerode" - Gottfried Vossen, Kurt-Ulrich Witt (2016). ''Grundkurs Theoretische Informatik. Eine anwendungsbezogene Einführung – Für Studierende in allen Informatik-Studiengängen''. 6., erweiterte und überarbeitete Auflage. Springer Vieweg. Seite 49.

"Satz von Myhill & Nerode" - Alexander Asteroth, Christel Baier (2002). ''Theoretische Informatik. Eine Einführung in Berechenbarkeit, Komplexität und formale Sprachen mit 101 Beispielen''. Pearson Studium. Seite 260. --Visualiser (Diskussion) 17:11, 12. Okt. 2023 (CEST)