---

Geschrieben von felix01992 am 02.12.2016 um 15:49:

  Beweis, dass es keinen DEA für verschiedene Sprachen gibt

Hey Forum,

ich stehe momentan u.a. vor der Aufgabe:

Beweise, dass es keinen DEA mit 3 Zuständen gibt, der die Sprache 0000Sigma^* erkennen kann, mit Sigma = {0,1}.

Wie beweist man so etwas? Soll ich zeigen, dass die Sprache nicht regulär ist (bspw. Pumping-Lemma mit Pumping-Zahl 3)? Falls das der richtige Gedanke sein sollte, wie läuft der Beweis dann mit einer festen Pumping-Zahl ab? Allgemein weiß ich zwar wie der Beweis durch PL geht, aber mit einer konkreten Zahl noch nicht... Oder gibt es einen "einfacheren" Weg?

Danke für eure Hilfe!

---

Geschrieben von eulerscheZahl am 02.12.2016 um 16:00:

 

Es gibt einen DEA, nur keinen mit 3 Zuständen. Somit ist deine Beweisidee hinfällig.
Versuche mal, einen DEA zu zeichnen

---

Geschrieben von felix01992 am 02.12.2016 um 16:16:

 

Danke schonmal für deine Antwort!
Ich hab grade probiert einen Automaten zu zeichnen, das geht mit 3 Zuständen aber auf keinen Fall. Bei 3 Zuständen hat man ja nur 2 Übergänge und kann somit nur zwei Nullen konkatenieren bevor man dann die Schleife (0,1) auf den dritten Zustand anwenden kann...

---

Geschrieben von eulerscheZahl am 02.12.2016 um 16:18:

 

Jetzt hast du es

---

Geschrieben von felix01992 am 02.12.2016 um 16:23:

 

Oh, das war es schon? Gibt es eine formale Beweisführung oder reicht mein Ansatz (richtig ausgeschrieben) so aus?
Vielen Dank nochmal

---

Geschrieben von eulerscheZahl am 02.12.2016 um 16:45:

 

Wie man das noch formalisieren kann und wie exakt es von dir erwartet wird weiß ich auch nicht.