Die letzten 6 Beiträge |
eulerscheZahl |
Wie man das noch formalisieren kann und wie exakt es von dir erwartet wird weiß ich auch nicht. |
felix01992 |
Oh, das war es schon? Gibt es eine formale Beweisführung oder reicht mein Ansatz (richtig ausgeschrieben) so aus?
Vielen Dank nochmal
|
eulerscheZahl |
Jetzt hast du es
|
felix01992 |
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... |
eulerscheZahl |
Es gibt einen DEA, nur keinen mit 3 Zuständen. Somit ist deine Beweisidee hinfällig.
Versuche mal, einen DEA zu zeichnen |
felix01992 |
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! |
|
|