Pumping Lemma für Reg. Spr. < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:56 Mi 06.05.2009 | | Autor: | RalU |
| Aufgabe | | Beh.: L={ [mm] 0^{l}1^{m}2^{k}|l,m,k \in \IN [/mm] und l > k } |
Beh.: L ist nicht regulär
Bew. mittels Pumping Lemma für reg. Sprachen
(Beweis durch Kontraposition und zeigen, dass das PL nicht gillt)
Angenommen L wäre regulär.
a) sei n eine beliebiege Konstante aus dem PL
b) Wähle w=def [mm] 0^{n+1}1 2^{n}. [/mm]
Dann ist [mm] |w|\ge [/mm] n und w [mm] \in [/mm] L
c) Sei w=xyz eine bel. Zerlegung
d)(es wird folgende Zerlegung gewählt):
[mm] |-0^{n+1}-|-1-|-2^{n}-|
[/mm]
|-x----|-y-|--z--|
Wegen (1) des PL ((1) y [mm] \not= \varepsilon)
[/mm]
besteht y aus mind. einer "0".
Wegen (2) des PL ((2) [mm] |xy|\le [/mm] n )
besteht xy nur aus "0"en.
(3) des PL behauptet, dass [mm] \forall_{i\ge 0} [/mm] ist [mm] xy^{i}z \in [/mm] L
wähle i=0
Dann hat [mm] xy^{0}z [/mm] genau n+1-|y| [mm] \le [/mm] n viele =0en aber n viele 2en.
Also ist [mm] xy^{0} \not\in [/mm] L
-> L ist nicht regulär. #
Meine Fragen:
Warum folgt aus "Dann hat [mm] xy^{0}z [/mm] genau n+1-|y| [mm] \le [/mm] n viele =0en aber n viele 2en." -> Also ist [mm] xy^{0} \not\in [/mm] L ???
Einfach nur, weil dann die Bedingung der Sprache L l > k nicht mehr erfüllt ist?
Was wäre denn, wenn ich über das PL den Nachweis einer ganz einfachen Sprache, von der ich eigentlich weiß, dass sie regulär ist, (z.B. L={a}) nachweisen müsste.
Dann kann ich doch so wie im Pl gefordert gar kein Teilwort xyz bilden, weil L gar nicht lang genug ist, geschweige denn die Bedingungen (2) und (3) des PL prüfen....?!?
Oder brauch ich für die Teilwortbildung im PL nicht mind. die Länge 3???
Gruß, Ralf
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:14 Do 07.05.2009 | | Autor: | thane |
Hallo Ralf,
> Bew. mittels Pumping Lemma für reg. Sprachen
>
> (Beweis durch Kontraposition und zeigen, dass das PL nicht
> gillt)
>
> Angenommen L wäre regulär.
> a) sei n eine beliebiege Konstante aus dem PL
> b) Wähle w=def [mm]0^{n+1}1 2^{n}.[/mm]
> Dann ist [mm]|w|\ge[/mm] n und w [mm]\in[/mm] L
> c) Sei w=xyz eine bel. Zerlegung
> d)(es wird folgende Zerlegung gewählt):
> [mm]|-0^{n+1}-|-1-|-2^{n}-|[/mm]
> |-x----|-y-|--z--|
>
> Wegen (1) des PL ((1) y [mm]\not= \varepsilon)[/mm]
> besteht y aus
> mind. einer "0".
> Wegen (2) des PL ((2) [mm]|xy|\le[/mm] n )
> besteht xy nur aus "0"en.
>
> (3) des PL behauptet, dass [mm]\forall_{i\ge 0}[/mm] ist [mm]xy^{i}z \in[/mm]
> L
>
> wähle i=0
> Dann hat [mm]xy^{0}z[/mm] genau n+1-|y| [mm]\le[/mm] n viele =0en aber n
> viele 2en.
> Also ist [mm]xy^{0} \not\in[/mm] L
> -> L ist nicht regulär. #
> Meine Fragen:
> Warum folgt aus "Dann hat [mm]xy^{0}z[/mm] genau n+1-|y| [mm]\le[/mm] n
> viele =0en aber n viele 2en." -> Also ist [mm]xy^{0} \not\in[/mm] L
> ???
>
> Einfach nur, weil dann die Bedingung der Sprache L l > k
> nicht mehr erfüllt ist?
![[ok]](/images/smileys/ok.gif "[ok]") Richtig, denn wenn diese Bedingung nicht erfüllt ist, dann liegt das Wort ja nicht in der Sprache.
> Was wäre denn, wenn ich über das PL den Nachweis einer ganz
> einfachen Sprache, von der ich eigentlich weiß, dass sie
> regulär ist, (z.B. L={a}) nachweisen müsste.
> Dann kann ich doch so wie im Pl gefordert gar kein
> Teilwort xyz bilden, weil L gar nicht lang genug ist,
> geschweige denn die Bedingungen (2) und (3) des PL
> prüfen....?!?
> Oder brauch ich für die Teilwortbildung im PL nicht mind.
> die Länge 3???
Zunächsteinmal wird ja nur gefordert, dass $|y| [mm] \not= [/mm] 0$ ist. Also kannst du x und z als leeres Wort wählen.
Beachte aber, dass du mit dem Pumping Lemma nicht zeigen kannst, dass eine Sprache regulär ist. Es gilt nur die Implikation:
L regulär => Pumping Lemma ist erfüllt.
Es gibt auch Sprachen, die das Pumping Lemma erfüllen aber nicht regulär sind.
Gruß,
thane
|
|
|
|
