PumpingLemma Beweise < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:13 Sa 20.02.2010 | | Autor: | RalU |
| Aufgabe | Hallo,
Es geht um folgende zwei Teilaufgaben
Behauptung jeweils [mm] L_{i} [/mm] regulär
L1={w [mm] \in [/mm] { a,b } ^{*} | [mm] w^{R}=w [/mm] }
L2={ [mm] 0^{l}1^{m}2^{k} [/mm] | l,m,k [mm] \in \IN [/mm] und l > k }
Mit Hilfe des Pumping Lemmas soll gezeigt werden, dass die Sprachen jeweils nicht regulär sind. |
zu L1)
Beh. L1 nicht regulär
Bew.: Knotraposition des Pumping lemmas
Angenommen, L1 wäre regulär.
Dann sei n [mm] \in \IN [/mm] \ {0} eine beliebige Konstante aus dem PL.
Dann gilt für alle Wörter w [mm] \in [/mm] L1 mit |w|>=n:
Es existiert eine Zerlegung aus x,y,z mit w=xyz, so dass
(1) y [mm] \not= \varepsilon [/mm] und
(2) |xy|<=n und
(3) [mm] \forall [/mm] i [mm] \in \IN [/mm] ist [mm] xy^{i}z \in [/mm] L1.
wähle [mm] w=a^{n}ba^{n}. [/mm] Dann ist w [mm] \in [/mm] L1 und |w| >= n.
wähle folgende Zerlegung von w:
| [mm] a^{n}ba^{n}|
[/mm]
| | |
|xy| z |
Dann ist y [mm] \not= \varepsilon [/mm] weil y aus mindestens einem a besteht. (1) Bed. oben erfüllt.
Weiter besteht |xy| nur aus a's (insgesamt n). Somit gilt auch (2) |xy|<=n.
wähle i=0.
Für [mm] xy^{0}z [/mm] gilt dann: |xy| besteht aus n-1 a's aber z aus b und n a's. (n-1 a's vor dem b und n a's hinter dem b). Damit ist (3) aus dem PL nicht erfüllt, da das gewählte Wort [mm] \not \in [/mm] L2. Somit ist L2 nicht regulär. q.e.d.
Meine Frage: i=2 dürfte ich doch z.b. nicht wählen, weil dann ja da steht [mm] xy^{2}z [/mm] und |xy|<=n ( (2) aus dem PL ) nicht mehr erfüllt wäre, oder? Also |xy| bestünde ja dann aus n +|y| a's (also |xy|>n). Dann ist aber |xy| nicht <=n (2 Bed. aus PL) nicht erfüllt...
für L2) sähe der Beweis ähnlich aus. Ich würde dann
folgendes Wort w wählen: [mm] w=0^{n}1^{m}2^{n-1}
[/mm]
Dann gibt es folgende Zerlegung x,y,z:
[mm] |0^{n}1^{m}s^{n-1}|
[/mm]
xy|z
Dann ist y [mm] \not [/mm] = [mm] \varepsilon, [/mm] da es aus mindestens einem a besteht und |xy| <=n, da aus insgesamt n a's.
Wähle i=0 . Dann gilt [mm] xy^{i}z [/mm] aus dem PL nicht, weil |xy| aus n-|y| a's und z aus n-1 a's. Also ist l<=k und deshalb L2 nicht regulär. q.e.d.
Auch hier wieder die Frage: wenn ich oben mein Wort w so wählen würde: [mm] w=0^{n+1}1^{m}2^{n}, [/mm] dann wäre ja w>=n zwar erfüllt. Aber ich muss ja die Zerlegung in x,y,z gleich lassen, also:
[mm] |0^{n+1}1^{m}2^{n}|
[/mm]
xy|z
Dann ist aber |xy| nicht <=n (2 Bed. aus PL) nicht erfüllt...
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:12 So 21.02.2010 | | Autor: | felixf |
Hallo!
> Es geht um folgende zwei Teilaufgaben
> Behauptung jeweils [mm]L_{i}[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
regulär
> L1={w [mm]\in[/mm] { a,b } ^{*} | [mm]w^{R}=w[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
}
> L2={ [mm]0^{l}1^{m}2^{k}[/mm] | l,m,k [mm]\in \IN[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
und l > k }
>
> Mit Hilfe des Pumping Lemmas soll gezeigt werden, dass die
> Sprachen jeweils nicht regulär sind.
> zu L1)
> Beh. L1 nicht regulär
> Bew.: Knotraposition des Pumping lemmas
>
> Angenommen, L1 wäre regulär.
> Dann sei n [mm]\in \IN[/mm] \ {0} eine beliebige Konstante aus dem
> PL.
Das ist etwas unschoen formuliert. Schreibe sowas wie: "Sei $n$ die Konstante aus dem PL."
> Dann gilt für alle Wörter w [mm]\in[/mm] L1 mit |w|>=n:
> Es existiert eine Zerlegung aus x,y,z mit w=xyz, so dass
> (1) y [mm]\not= \varepsilon[/mm] und
> (2) |xy|<=n und
> (3) [mm]\forall[/mm] i [mm]\in \IN[/mm] ist [mm]xy^{i}z \in[/mm] L1.
>
> wähle [mm]w=a^{n}ba^{n}.[/mm] Dann ist w [mm]\in[/mm] L1 und |w| >= n.
Soweit so gut.
> wähle folgende Zerlegung von w:
>
> | [mm]a^{n}ba^{n}|[/mm]
> | | |
> |xy| z |
Du kannst nicht einfach eine Zerlegung waehlen. Das PL sagt, dass es eine Zerlegung gibt die das erfuellt. Nicht dass es jede beliebige Zerlegung tut.
Es kann naemlich sein, dass $|x y| < n$ ist; dann ist $z$ von der Form [mm] $a^m [/mm] b [mm] a^n$. [/mm] Aber das reicht schon voellig aus.
>
> Dann ist y [mm]\not= \varepsilon[/mm] weil y aus mindestens einem a
> besteht. (1) Bed. oben erfüllt.
> Weiter besteht |xy| nur aus a's (insgesamt n). Somit gilt
> auch (2) |xy|<=n.
>
> wähle i=0.
> Für [mm]xy^{0}z[/mm] gilt dann: |xy| besteht aus n-1 a's
aus hoechstens $n - 1$ a's.
> aber z aus
> b und n a's. (n-1 a's vor dem b und n a's hinter dem b).
> Damit ist (3) aus dem PL nicht erfüllt, da das gewählte
> Wort [mm]\not \in[/mm] L2. Somit ist L2 nicht regulär. q.e.d.
Du meinst L1 und nicht L2
> Meine Frage: i=2 dürfte ich doch z.b. nicht wählen, weil
> dann ja da steht [mm]xy^{2}z[/mm] und |xy|<=n ( (2) aus dem PL )
> nicht mehr erfüllt wäre, oder?
Doch, das darfst du so machen. Du kannst jedes $i$ waehlen, ausser $i = 1$. Das Ergebnis ist immer ein Wort, welches nicht in L2 liegt.
> Also |xy| bestünde ja
> dann aus n +|y| a's (also |xy|>n). Dann ist aber |xy| nicht
Also $x [mm] y^2$ [/mm] besteht aus [mm] $\le [/mm] n + |y|$ a's, aber $x y$ besteht immer noch aus [mm] $\le [/mm] n$ a's.
> für L2) sähe der Beweis ähnlich aus. Ich würde dann
> folgendes Wort w wählen: [mm]w=0^{n}1^{m}2^{n-1}[/mm]
>
> Dann gibt es folgende Zerlegung x,y,z:
> [mm]|0^{n}1^{m}s^{n-1}|[/mm]
> xy|z
Hier hast du genau das gleiche Problem wie oben. Was du aber ebenfalls sehr einfach umgehen kannst.
> Dann ist y [mm]\not[/mm] = [mm]\varepsilon,[/mm] da es aus mindestens einem a
> besteht und |xy| <=n, da aus insgesamt n a's.
>
> Wähle i=0 . Dann gilt [mm]xy^{i}z[/mm] aus dem PL nicht, weil |xy|
> aus n-|y| a's und z aus n-1 a's. Also ist l<=k und deshalb
> L2 nicht regulär. q.e.d.
Hier ebenfalls die gleichen Probleme wie oben.
> Auch hier wieder die Frage: wenn ich oben mein Wort w so
> wählen würde: [mm]w=0^{n+1}1^{m}2^{n},[/mm] dann wäre ja w>=n
> zwar erfüllt. Aber ich muss ja die Zerlegung in x,y,z
> gleich lassen, also:
> [mm]|0^{n+1}1^{m}2^{n}|[/mm]
> xy|z
> Dann ist aber |xy| nicht <=n (2 Bed. aus PL) nicht
> erfüllt...
Wie schon gesagt: du kannst dir die Zerlegung nicht aussuchen.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:25 So 21.02.2010 | | Autor: | RalU |
> > wähle folgende Zerlegung von w:
> >
> > | [mm]a^{n}ba^{n}|[/mm]
> > | | |
> > |xy| z |
>
> Du kannst nicht einfach eine Zerlegung waehlen. Das PL
> sagt, dass es eine Zerlegung gibt die das erfuellt. Nicht
> dass es jede beliebige Zerlegung tut.
>
> Es kann naemlich sein, dass [mm]|x y| < n[/mm] ist; dann ist [mm]z[/mm] von
> der Form [mm]a^m b a^n[/mm]. Aber das reicht schon voellig aus.
>
Hier weiß ich nicht genau, wie du das meinst. Ich muss doch an der Stelle mal eine Zerlegung wählen, die das PL erfüllt, damit ich überhaupt weiter machen kann...
Wie hätte ich denn sollen an der Stelle weitermachen?
Als Antwort auf meine Fragen bezüglich Wahl des i's bei [mm] xy^{i}z [/mm] hast du geschrieben, dass es egal ist, welches i ich wähle. Daraus schließe ich, dass die Bedingung |xy|<=n unabhängig von der Wahl des i zu prüfen ist. Also wähle ich mein i z.B. mit i=2 oder beliebig anders dann gilt immer noch |xy|<=n, weil ich ja im Grunde immer [mm] |x^{1}y^{1}| [/mm] <=n zu prüfen hab...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:06 Mo 22.02.2010 | | Autor: | felixf |
Hallo!
> > > wähle folgende Zerlegung von w:
> > >
> > > | [mm]a^{n}ba^{n}|[/mm]
> > > | | |
> > > |xy| z |
> >
> > Du kannst nicht einfach eine Zerlegung waehlen. Das PL
> > sagt, dass es eine Zerlegung gibt die das erfuellt. Nicht
> > dass es jede beliebige Zerlegung tut.
> >
> > Es kann naemlich sein, dass [mm]|x y| < n[/mm] ist; dann ist [mm]z[/mm] von
> > der Form [mm]a^m b a^n[/mm]. Aber das reicht schon voellig aus.
>
> Hier weiß ich nicht genau, wie du das meinst. Ich muss
> doch an der Stelle mal eine Zerlegung wählen, die das PL
> erfüllt, damit ich überhaupt weiter machen kann...
> Wie hätte ich denn sollen an der Stelle weitermachen?
Na, wenn du eine solche Zerlegung hast, dann weisst du nur, das folgendes gilt:
Es gibt $k, [mm] \ell \in \IN$, [/mm] $k [mm] \ge [/mm] 0$, [mm] $\ell \ge [/mm] 1$, $k + [mm] \ell \le [/mm] n$ mit $x = [mm] a^k$, [/mm] $y = [mm] a^\ell$, [/mm] $z = [mm] a^{n - k - \ell} [/mm] b [mm] a^n$.
[/mm]
> Als Antwort auf meine Fragen bezüglich Wahl des i's bei
> [mm]xy^{i}z[/mm] hast du geschrieben, dass es egal ist, welches i
> ich wähle. Daraus schließe ich, dass die Bedingung
> |xy|<=n unabhängig von der Wahl des i zu prüfen ist.
In der Bedingung kommt kein $i$ vor. Sie hat also gar nichts mit $i$ zu tun.
> Also
> wähle ich mein i z.B. mit i=2 oder beliebig anders dann
> gilt immer noch |xy|<=n, weil ich ja im Grunde immer
> [mm]|x^{1}y^{1}|[/mm] <=n zu prüfen hab...
Die Zerlegung $w = x y z$ und die Eigenschaften davon, naemlich $|x y| [mm] \le [/mm] n$, ..., haben nichts mit $i$ zu tun.
LG Felix
|
|
|
|
