Pumping Lemma < Sonstige < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:06 Mo 27.06.2011 | | Autor: | bandchef |
| Aufgabe | Beweisen oder widerlegen sie mit Hilfe des Pumping Lemmas folgende Sprache:
[mm] $L=\left{ 0^j1^k0^l | k=j+l$ für $j,k,l \in \mathbb N \right} [/mm] |
Hi Leute!
Ich hab große Problem damit. Könnt ihr mir helfen?
Ich hab so angefangen:
Annahme: L ist regulär
Es existiert ein [mm] $n_0 \in \mathbb [/mm] N$
[mm] $\forall [/mm] z [mm] \in [/mm] L$ mit $|z| [mm] \geq n_0$ [/mm] mit u,v,w [mm] \in \Sigma_{\text{Bool}}^{\star}$
[/mm]
Wie geht's da jetzt wetier?
Kann mir jemand helfen?
|
|
| |
|
Hallo bandchef,
du bist doch nun schon lange genug im Forum dabei, dass du sicher schon den Formeleditor und die Vorschaufunktion entdeckt hast ...
Bitte editiere deine Frage und behebe alle Formatierungsfehler!
Danke!
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:55 Mo 27.06.2011 | | Autor: | felixf |
Moin!
> Beweisen oder widerlegen sie mit Hilfe des Pumping Lemmas
> folgende Sprache:
>
> [mm]$L=\left{ 0^j1^k0^l | k=j+l$ für $j,k,l \in \mathbb N \right}[/mm]
>
> Hi Leute!
>
> Ich hab große Problem damit. Könnt ihr mir helfen?
>
> Ich hab so angefangen:
>
>
> Annahme: L ist regulär
>
> Es existiert ein [mm]n_0 \in \mathbb N[/mm]
>
> [mm]$\forall[/mm] z [mm]\in[/mm] L$ mit $|z| [mm]\geq n_0$[/mm] mit u,v,w [mm]\in \Sigma_{\text{Bool}}^{\star}$[/mm]
>
>
> Wie geht's da jetzt wetier?
Na, so wie immer! Ist doch nicht das erste mal, dass du das Pumping-Lemma verwendest.
Du konstruierst ein Wort (in Abhaengigkeit von [mm] $n_0$), [/mm] so dass fuer jede Zerlegung die im Pumping-Lemma auftreten kann die aufgepumpte Version nicht mehr in der Sprache ist.
Wie koennte so ein Wort denn aussehen? Und wenn du das nicht weisst: wie sieht die Zerlegung denn aus? Oben hast du es ja sehr unvollstaendig hingeschrieben.
LG Felix
|
|
|
|
