Beweis, dass es keinen DEA für verschiedene Sprachen gibt |
| 02.12.2016, 15:49 | Auf diesen Beitrag antworten » |
| 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! |
|
|
|
| 02.12.2016, 16:00 | Auf diesen Beitrag antworten » |
| eulerscheZahl | Es gibt einen DEA, nur keinen mit 3 Zuständen. Somit ist deine Beweisidee hinfällig. Versuche mal, einen DEA zu zeichnen |
| 02.12.2016, 16:16 | Auf diesen Beitrag antworten » |
| 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... |
| 02.12.2016, 16:18 | Auf diesen Beitrag antworten » |
| eulerscheZahl | Jetzt hast du es 
|
| Anzeige | |
|
|
|
| 02.12.2016, 16:23 | Auf diesen Beitrag antworten » |
| felix01992 | 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:45 | Auf diesen Beitrag antworten » |
| eulerscheZahl | Wie man das noch formalisieren kann und wie exakt es von dir erwartet wird weiß ich auch nicht. |
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
