---

Geschrieben von Ikarus am 24.11.2011 um 23:06:

  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.

---

Geschrieben von Karlito am 24.11.2011 um 23:59:

  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

---

Geschrieben von Ikarus am 25.11.2011 um 00:29:

 

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?

---

Geschrieben von Karlito am 25.11.2011 um 08:31:

 

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

---

Geschrieben von Ikarus am 25.11.2011 um 10:15:

 

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?

---

Geschrieben von Karlito am 25.11.2011 um 12:14:

 

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