Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:29 Fr 12.09.2008 | | Autor: | TTaylor |
| Aufgabe | Sprache L
[mm]L= {a^{2m} b^m}[/mm]; m Element N |
Ich nehme an, dass L regulär ist. Es muss also eine Zahl n geben, so dass alle Wörter von L mit |x| >=n sich zerlegen lassen in x=uvw.
mit folgenden Eigenschaften:
1. |v|>=1
2. |uv| <= n
3. für alle i =0,1,2... [mm] uv^iw [/mm] Element L
Was muss ich an dieser Stelle für ein n wählen?
Wähle ich z.B. n=17 dann habe ich z.B. 12 a's und 6 b's.
Da |uv|<=17 sein muss und |v|>=1
Ich verstehe nicht wie darauf komme, dass wegen |uv| <= n und |v|>=1 folgt, dass |uv| nur aus a's bestehen muss?
Hoffe es kann mir jemand weiterhelfen.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 20:19 Fr 12.09.2008 | | Autor: | Framl |
Hi,
Du sollst zeigen, dass die Sprache L nicht regulär ist.
Dafür nimmst du einmal an, es wäre regulär. Dann gilt aber lt. Pummping-Lemma genau die Eigenschaften, die du aufgelistet hast und zwar gilt dies für jedes Wort mit [mm] $|x|\geq [/mm] n$.
Da du ja zeigen sollst, dass die Sprache nicht regulär ist, musst du obiges zum Widerspruch führen.
Du nimmst also eine beliebige natürliche Zahl (damit auch diejenige, die laut P.L. existieren muss - also das n) und wählst dir ein Wort aus der Sprache mit Länge [mm] $\geq [/mm] n$.
Wähle z.B. [mm] $x=a^{2n}b^n$. [/mm] Dieses liegt auf jeden Fall in der Sprache und die Länge ist [mm] $=3n\geq [/mm] n$. Damit gilt mit den von dir notierten Eigenschaften:
Es gibt eine Zerlegung $x=uvw$, sodass für jedes $i=0,1,2,...$ auch $uv^iw$ in der Sprache ist, wobei [mm] $1\leq |v|\leq |uv|\leq [/mm] n$.
Was passiert denn jetzt wenn du $i=0$ wählst? Liegt das Wort dann immer noch in der Sprache? Wenn nein ( ) wieso nicht?
Wenn du das gezeigt hast, bist du fertig. Denn dann stimmt die Aussage des Pummping Lemmas also doch nicht (du hast für jedes n gezeigt, dass es ein Wort gibt, sodass es eine Zerlegung gibt, die sich nicht auf- bzw. abpumpen lässt). Damit ist die Sprache nicht regulär.
Gruß Framl
|
|
|
|
