Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Ist die Sprache [mm] L=(a^{i}b^{j}c^{i+k} [/mm] | i,j,k > 0 ) regulär? Beweisen Sie!
Beweis mit Pumping Lemma
Behauptung: L ist nicht Regulär
Beweis durch widerspruch
Annahme: L ist regulär
Es existiert ein endlicher Automat mit z zuständen der L erkennt. Wähle wort n > z
[mm] \Rightarrow [/mm] daraus folgt, Automat hat mind. 1 Schleife.
1. Fall: Schleife erkennt mehrere Symbole [mm] \Rightarrow [/mm] mehrfach gemischte Folge
2. Fall: Schleifen für a und c unabhängig voneinander
[mm] \Rightarrow [/mm] a-Schleife kann öfter durchlaufen werden als c-schleife [mm] \Rightarrow [/mm] mehr a's als c's
[mm] \Rightarrow [/mm] Es existiert kein endlicher Automat für L
[mm] \Rightarrow [/mm] L ist nicht regulär. |
Wie genau muss ich mir die 1. Schleife denn vorstellen?
Und wie die 2. ? Ich kann mir in etwa vorstellen wie das ganze aussehen muss und ich weiß warum die Sprache nicht regulär ist aber ich kann mir unter den gestellten Fällen gerade absolut nichts vorstellen. Könnte mir da einer einen Denkanstoß geben?
Gruß,
Obi
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Do 15.11.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
