Pumping-Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Aufgabe | Beweisen Sie mit dem Pumping-Lemma:
[mm] $L=\{ 0^n 1 0^n | n \geq 1 \}$ [/mm] |
Hi Leute!
Ich hab Probleme mit dem Pumpuing-Lemma:
Sei n die Konstante des Pumping-Lemma für das gilt: $|xy| [mm] \leq [/mm] n$. Sowie w=xyz.
Zerlegung: [mm] $w=0^{n_1}0^{n_2}0^{n_3}10^n$ [/mm] mit [mm] $n_1 [/mm] + [mm] n_2 [/mm] + [mm] n_3 [/mm] = n$
Wie geht's hier nun weiter?
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 19:13 So 13.05.2012 | Autor: | felixf |
Moin!
> Beweisen Sie mit dem Pumping-Lemma:
>
> [mm]L=\{ 0^n 1 0^n | n \geq 1 \}[/mm]
Da fehlt irgendwas, oder?
Sollst du zeigen, dass $L$, welches ueber die Menge auf der rechten Seite definiert ist, nicht regulaer ist?
Oder sollst du zeigen, dass der Ausdruck in der Menge gleich der Sprache $L$ ist, deren Definition du hier nicht angibst?
LG Felix
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 15:53 Mo 14.05.2012 | Autor: | msg08 |
Pumping Lemma, Automat hat Zyklus. Also y ist entweder linke Seite, Mischung aus beidem oder rechter Seite.
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 17:20 Di 15.05.2012 | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|