Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | L = { [mm] a^n b^m c^n [/mm] | n,m > 0 } |
Hallo,
ich versuche mit dem Pumping Lemma für reg. Sprachen zu beweisen, dass diese Sprache nicht reg. ist.
Beweise waren noch nie meine Stärke.. hoffe daher wenigstens bischen richtig zu liegen :)
So wie ich das verstanden habe, muss ich mir nun ein beliebiges Wort aus dieser Sprache nehmen, dass von n abhängt.
z.B.:
x = [mm] a^n c^m b^n \in [/mm] L
Mein Wort x besteht aus uvw. Also x = uvw.
Wähle nun
u = [mm] \varepsilon
[/mm]
v = [mm] a^n [/mm] ( |v| [mm] \ge [/mm] 1 ist somit erfüllt)
Die Vorraussetzung uv [mm] \le [/mm] n ist auch erfüllt.
w = [mm] c^m b^n
[/mm]
Allg. gilt ja [mm] uv^{i}w \in [/mm] L für i [mm] \in \IN_{0}
[/mm]
Wenn ich jetzt i = 1 nehme,
erhalte ich
x = [mm] a^n c^m b^n \in [/mm] L
i=0 liefert:
x = [mm] c^m b^n \not\in [/mm] L
i=2 liefert
x = [mm] a^{2n} c^m b^n \not\in [/mm] L
Wegen i=0 und i=2 habe ich einen Widerspruch und somit den Beweis erbracht(?).
Ist das korrekt?
Vielen Dank
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Di 22.09.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:35 Mi 25.11.2009 | | Autor: | mangaka |
Hi,
Dass du ein Wort der Sprache suchst, das abhängig von n ist, ist schon einmal der richtige Weg.
Aber du hast einen kleinen Fehler in deinem Beweis. Du musst zeigen, dass für jede mögliche Zerlegung deines Wortes, das aufgepumpte Wort nicht in der Sprache liegt.
Du hast nur eine Zerlegung angegeben.
Insgesamt gibt es diese:
1)$uvw = [mm] a^i [/mm] + [mm] b^j$ [/mm] mit$ i+j [mm] \leq [/mm] n$
2)$uvw = [mm] a^i [/mm] + [mm] b^j+ c^k$ [/mm] mit $i+j+k [mm] \leq [/mm] n$
3)$uvw = [mm] b^i [/mm] + [mm] c^j$ [/mm] mit $i+j [mm] \leq [/mm] n$
Jetzt brauchst du nur noch zu überlegen, wieso die aufgepumpten Wörter dieser Zerlegungen keine Wörter der Sprache sind.
|
|
|
|
