 NEA mit nur einem Endzustand erkennt jede Sprache? |
Ikarus
Grünschnabel
Dabei seit: 24.11.2011
Beiträge: 3
 |
|
| 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:06 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
| 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
|
|
|
24.11.2011 23:59 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
25.11.2011 08:31 |
|
|
Ikarus
Grünschnabel
Dabei seit: 24.11.2011
Beiträge: 3
|
|
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 10:15 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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 
|
|
|
25.11.2011 12:14 |
|
|
|
