NEA mit nur einem Endzustand erkennt jede Sprache?

24.11.2011, 23:06	Auf diesen Beitrag antworten »
Ikarus	NEA mit nur einem Endzustand erkennt jede Sprache? Meine Frage: Hallo, meine Frage lautet: Gibt es eine erkennbare Sprache, die nicht von einem NEA mit nur einem Endzustand erkannt werden kann? (Keine Wortübergänge, Keine Epsilon-NEA's) Meine Ideen: Ich glaub mein Ansatz führt zu einem Teufelskreis. Wenn ich einen NEA mit mehreren Endzuständen habe und dort einfach alle EZ per Epsilon-Kanten zu einem neuen EZ führe. Und diesen Epsilon-NEA zu einem normalen NEA umwandel, dann hat der am Ende ja wieder zwei EZ.


24.11.2011, 23:59	Auf diesen Beitrag antworten »
Karlito	RE: NEA mit nur einem Endzustand erkennt jede Sprache? Schon das Thema vor dir durchgelesen? Versuche einen NEA zu finden, welcher deinen Ansprüchen genügt und nur aus den Worten (ab)* oder (cd)* oder dem leeren Wort besteht (Vereinigung der 3 Möglichkeiten). Das sollte nicht mit nur einem EZ gehen. VG, Karlito
25.11.2011, 00:29	Auf diesen Beitrag antworten »
Ikarus	Bitte entschuldige, wenn ich hier mir Ideen komme, die vielleicht ziemlich dumm sind. Aber ich bin noch neu in dem Thema. Meiner Meinung nach erkennt dieser NEA doch die Sprache mithilfe eines EZ oder nicht?
25.11.2011, 08:31	Auf diesen Beitrag antworten »
Karlito	Er erkennt zwar die Sprache, aber auch noch mehr... In deiner Sprache ist auch das Wort abcd enthalten. Die Sprache, die ich meine enthält nur Wörter der Form abab...ab und cdcd...cd und das leere Wort. VG, Karlito
Anzeige

25.11.2011, 10:15	Auf diesen Beitrag antworten »
Ikarus	Ja stimmt. Ist das die einzige Möglichkeit für so einen NEA? Oder kann man eine allgemein geltende Regel für solche NEA's aufstellen?
25.11.2011, 12:14	Auf diesen Beitrag antworten »
Karlito	Sry, das Handwerkszeug hast du ja. Wenn du meinen Automaten verstanden hast, solltest du in der Lage sein, dir eine Beschreibung auszudenken. VG, Karlito + Rechtschreibgehilfe

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »