|
  |
 Beweis, dass es keinen DEA für verschiedene Sprachen gibt |
felix01992
unregistriert
 |
|
| 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!
|
|
02.12.2016 15:49 |
|
|
felix01992
unregistriert
|
|
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...
|
|
|
02.12.2016 16:16 |
|
|
felix01992
unregistriert
|
|
Oh, das war es schon? Gibt es eine formale Beweisführung oder reicht mein Ansatz (richtig ausgeschrieben) so aus?
Vielen Dank nochmal 
|
|
|
02.12.2016 16:23 |
|
|
|
|
|
|
|
|
