Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:59 Mo 13.05.2013 | | Autor: | bandchef |
Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
| Aufgabe | | Zeigen Sie, dass die Sprache $L=\{aa | a \in \{0,1\}^{\*}\}$ nicht kontextfrei ist. |
Sei $L$ eine kontextfreie Sprache, dann gibt es eine Konstante $n \in \mathbb N$, so dass sich jedes $z \in L$ mit $|z|\geq n$, so als z=uvwxy schreiben lässt, dass $|vwx|\leq n$, $|vx|\geq 1$ und $u v^i w x^i y \in L$ für alle $i \geq 0$ gilt:
wähle: $z = a^n a^n$, $|z| = n+n = 2n \geq n$
$z = u v^i w x^i y = a^{|u|+i|v|+|w| + i|x|} a^{|y|}$
Dieses Wort liegt genau dann nicht in L, wenn: $|u|+i|v|+|w| + i|x|} = n \Leftrightarrow ... \Leftrighttarow i = \frac{n-|u|-|w|}{|vx|}$
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:12 Di 14.05.2013 | | Autor: | tobit09 |
Hallo bandchef,
> Sei [mm]L[/mm] eine kontextfreie Sprache, dann gibt es eine
> Konstante [mm]n \in \mathbb N[/mm], so dass sich jedes [mm]z \in L[/mm] mit
> [mm]|z|\geq n[/mm], so als z=uvwxy schreiben lässt, dass [mm]|vwx|\leq n[/mm],
> [mm]|vx|\geq 1[/mm] und [mm]u v^i w x^i y \in L[/mm] für alle [mm]i \geq 0[/mm]
> gilt:
Angenommen $L$ wäre kontextfrei. Dann gäbe es eine Zahl [mm] $n\in\IN$ [/mm] mit der Eigenschaft aus dem Pumping Lemma.
> wähle: [mm]z = a^n a^n[/mm], [mm]|z| = n+n = 2n \geq n[/mm]
Die Wörter aus $L$ bestehen nicht aus Buchstaben namens $a$, sondern aus 0en und 1en!
(Ich tue jetzt so, als hättest du korrekterweise ein [mm] $z\in [/mm] L$ gewählt.)
Insbesondere besitzt unser $z$ die Gestalt $z=uvwxy$ mit [mm] $|vwx|\le [/mm] n$, [mm] $|vx|\ge [/mm] 1$ und [mm]u v^i w x^i y \in L[/mm] für alle [mm]i \geq 0[/mm].
> [mm]z = u v^i w x^i y = a^{|u|+i|v|+|w| + i|x|} a^{|y|}[/mm]
Schreibe nicht $z = u [mm] v^i [/mm] w [mm] x^i [/mm] y$! Das ist außer für $i=1$ falsch!
> Dieses Wort liegt genau dann nicht in L, wenn: [mm]|u|+i|v|+|w| + i|x|} = n[/mm]
Wie kommst du darauf?
> [mm]\Leftrightarrow ... \Leftrightarrow i = \frac{n-|u|-|w|}{|vx|}[/mm]
Diese Umformung stimmt.
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:12 Di 14.05.2013 | | Autor: | bandchef |
Behauptung: L ist nicht kontextfrei.
Sei [mm]L[/mm] eine kontextfreie Sprache, dann gibt es eine
Konstante [mm]n \in \mathbb N[/mm], so dass sich jedes [mm]z \in L[/mm] mit
[mm]|z|\geq n[/mm], so als z=uvwxy schreiben lässt, dass [mm]|vwx|\leq n[/mm],
[mm]|vx|\geq 1[/mm] und [mm]u v^i w x^i y \in L[/mm] für alle [mm]i \geq 0[/mm]
gilt:
wähle: [mm] $z=0^n1^n$, $|z|=n+n=2n\geq [/mm] n$
[mm] $z=\underbrace{0^{|u|} 0^{i|v|} 0^{|w|} 0^{i|x|}}_{\text{näher betrachten}} 1^n$
[/mm]
Dieses Wort liegt genau dann nicht in L, wenn $|u|+i|v|+|w|+i|x| = n [mm] \Leftrightarrow [/mm] |u| + i|vx| + |w| = n [mm] \Leftrightarrow [/mm] i = [mm] \frac{n-|u|-|w|}{|vx|}$, [/mm] da der vordere Wortteil nach dem Pumpen um den berechneten Wert von i größer ist. Da aber laut Sprache das vordere a (Wort bestehend aus 01) mit dem hinteren a (das gleiche Wort; ist ja auch das gleiche a) übereinstimmen muss, gilt dann: $z [mm] \notin [/mm] L$.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:22 Di 14.05.2013 | | Autor: | tobit09 |
> Behauptung: L ist nicht kontextfrei.
>
> Sei [mm]L[/mm] eine kontextfreie Sprache,
Angenommen $L$ wäre kontextfrei.
> dann gibt es eine
> Konstante [mm]n \in \mathbb N[/mm], so dass sich jedes [mm]z \in L[/mm] mit
> [mm]|z|\geq n[/mm], so als z=uvwxy schreiben lässt, dass [mm]|vwx|\leq n[/mm],
> [mm]|vx|\geq 1[/mm] und [mm]u v^i w x^i y \in L[/mm] für alle [mm]i \geq 0[/mm]
> gilt:
>
> wähle: [mm]z=0^n1^n[/mm], [mm]|z|=n+n=2n\geq n[/mm]
Das ist kein Element von $L$. Damit sagt das Pumping Lemma nichts über dieses Wort aus.
(Ich tue im Folgenden wieder so, als hättest du korrekterweise ein Wort [mm] $z\in [/mm] L$ gewählt.)
> [mm]z=\underbrace{0^{|u|} 0^{i|v|} 0^{|w|} 0^{i|x|}}_{\text{näher betrachten}} 1^n[/mm]
Es existiert eine Zerlegung $z=uvwxy$, aber es gilt doch nicht $z=uv^iwx^iy$ (außer für $i=1$)!
Außerdem: Warum sollte die Zerlegung so aussehen, dass gerade $uvwx$ dem "0-Teil" von $z$ entspricht und $y$ dem "1-Teil"?
> Dieses Wort liegt genau dann nicht in L, wenn
> [mm]|u|+i|v|+|w|+i|x| = n[/mm]
Quatsch. Wie kommst du darauf?
> [mm]\Leftrightarrow |u| + i|vx| + |w| = n \Leftrightarrow i = \frac{n-|u|-|w|}{|vx|}[/mm],
Dieser Äquivalenzumformung kann ich folgen.
> da der vordere Wortteil nach dem Pumpen um den berechneten
> Wert von i größer ist.
Was versuchst du gerade zu begründen?
> Da aber laut Sprache das vordere a
> (Wort bestehend aus 01) mit dem hinteren a (das gleiche
> Wort; ist ja auch das gleiche a) übereinstimmen muss, gilt
> dann: [mm]z \notin L[/mm].
Meinst du vielleicht [mm] $uv^iwx^iy\notin [/mm] L$? Mit [mm] $i:=\frac{n-|u|-|w|}{|vx|}$?
[/mm]
(Dann bräuchtest du noch, dass [mm] $i\in\IN_0$ [/mm] gilt.)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:31 Di 14.05.2013 | | Autor: | bandchef |
> Das ist kein Element von $L$.
Was wäre denn ein Element von L? Das vielleicht: [mm] $z=0^n1^n0^n1^n$? [/mm] Kannst du mir vielleicht mit ein paar gezielteren Tips draufhelfen?
> Es existiert eine Zerlegung $z=uvwxy$, aber es gilt doch nicht $z=uv^iwx^iy$ (außer für $i=1$)!
> Außerdem: Warum sollte die Zerlegung so aussehen, dass gerade $uvwx$ dem "0-Teil" von $z$ entspricht und $y$ dem "1-Teil"?
Ja, ich mein, irgendwie muss ich das ja aufteilen. Gibts da nicht irgendeine Regel für dieses "Wort Suchen, das in L liegt" und das "Aufteilen"? Ich komm da in 100 Jahren nicht damit zurecht...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:06 Di 14.05.2013 | | Autor: | tobit09 |
> > Das ist kein Element von [mm]L[/mm].
>
> Was wäre denn ein Element von L? Das vielleicht:
> [mm]z=0^n1^n0^n1^n[/mm]?
![[ok]](/images/smileys/ok.gif "[ok]") Das ist ein Element von $L$.
Das es für unsere Zwecke das Gewünschte leistet, ist allerdings alles andere als trivial. Ich habe gerade eine knappe Stunde mit vielen wieder verworfenen Versuchen gebraucht, um das einzusehen.
> > Es existiert eine Zerlegung [mm]z=uvwxy[/mm], aber es gilt doch
> nicht [mm]z=uv^iwx^iy[/mm] (außer für [mm]i=1[/mm])!
> > Außerdem: Warum sollte die Zerlegung so aussehen, dass
> gerade [mm]uvwx[/mm] dem "0-Teil" von [mm]z[/mm] entspricht und [mm]y[/mm] dem
> "1-Teil"?
>
> Ja, ich mein, irgendwie muss ich das ja aufteilen.
Nicht du teilst das auf. Die Wahl von $n$ liefert so eine Aufteilung.
> Gibts da
> nicht irgendeine Regel für dieses "Wort Suchen, das in L
> liegt" und das "Aufteilen"? Ich komm da in 100 Jahren nicht
> damit zurecht...
Allgemeingültige Regeln kenne ich nicht.
Zum [mm] "$z\in [/mm] L$ suchen": Ich probiere es meist zunächst mit irgendeinem möglichst einfachen Wort einer Länge [mm] $\ge [/mm] n$. Dann gucke ich, ob sich damit der gewünschte Widerspruch herleiten lässt. Wenn nicht, versuche ich zu "sehen", woran es scheitert und die Wahl von $z$ entsprechend anzupassen.
Zum "Aufteilen": Diese Bezeichnung finde ich schon irreführend, weil es ja nicht darum geht, selbst eine Aufteilung vorzunehmen, sondern über eine gegebene Aufteilung Aussagen zu treffen. Manchmal sind verschiedene Fälle denkbar, wie die Aufteilung aussehen könnte. Dann muss man alle diese Fälle durchgehen (wenn einem nicht gerade ein tolles Argument einfällt, mit denen sich mehrere Fälle auf einmal erledigen lassen).
> Kannst du mir vielleicht mit ein paar
> gezielteren Tips draufhelfen?
Ich habe keine Ahnung, ob es einfachere Lösungswege gibt. Ich bin jedenfalls wie folgt vorgegangen:
Ich habe die Fälle
1. "vwx liegt in der ersten Hälfte von z"
2. "vwx liegt in der zweiten Hälfte von z"
3. "vwx liegt teils in der ersten Hälfte, teils in der zweiten Hälfte von z"
unterschieden und jeweils [mm] $uv^0wx^0y\notin [/mm] L$ überlegt.
Angenommen [mm] $z':=uv^0wx^0y\in [/mm] L$.
Man kann sich überlegen, dass $2n<|z'|<4n$ gelten muss.
1. Fall: "vwx liegt in der ersten Hälfte von z"
Dann muss y auf [mm] $0^n1^n$ [/mm] enden.
Somit endet auch $z'$ auf [mm] $0^n1^n$.
[/mm]
Somit endet die zweite Hälfte von $z'$ auf 1 und die erste Hälfte von $z'$ auf 0 (für Letzteres beachte: Wegen $|z'|<4n$ hat die zweite Hälfte von $|z'|$ weniger als $2n$ Buchstaben.).
Also kann $z'$ nicht in $L$ liegen.
Den 2. Fall kann man ähnlich behandeln.
3. Fall: "vwx liegt teils in der ersten Hälfte, teils in der zweiten Hälfte von z"
vwx beginnt also innerhalb der ersten $n$ 1en von z und endet innerhalb der zweiten $n$ 0en von z.
Wegen [mm] $|vx|\ge [/mm] 1$ gilt [mm] $|v|\ge [/mm] 1$ oder [mm] $|x|\ge [/mm] 1$. Betrachten wir etwa den Fall [mm] $|v|\ge [/mm] 1$. (Den Fall [mm] $|x|\ge [/mm] 1$ kann man ähnlich behandeln.)
Dann hat v einen ersten Buchstaben und, da vwx innerhalb der ersten $n$ 1en von z beginnt, muss dieser erste Buchstabe eine 1 sein.
y endet auf mit n 1en (vwx kann wegen [mm] $|vwx|\le [/mm] n$ nicht bis in die letzten n 1en von z hineinragen).
Somit endet die zweite Hälfte von $z'$ mit n 1en, während die erste Hälfte von z' mindestens eine 1 weniger hat als die erste Hälfte von z (denn gegenüber z ist in z' die erste 1 von v entfernt).
Also [mm] $z'\notin [/mm] L$.
Ich würde sagen: Wenn es nicht irgendeinen einfacheren Weg gibt, den ich übersehe, ist diese Aufgabe zu schwer für eine Klausur.
Meine Ansätze sind auch nicht mit der sonst üblichen Präzision verfasst. Würde man das tun, würde man vermutlich viele Seiten vollschreiben.
Erhältst du eine Musterlösung? Falls ja, so wäre ich daran interessiert!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:50 Mi 15.05.2013 | | Autor: | bandchef |
> Somit endet die zweite Hälfte von $z'$ auf 1 und die erste Hälfte von $z'$ auf 0 (für Letzteres beachte:
Was meinst du mit zweiter Hälfte von $z'$? Das y besteht ja hier nun aus dem letzten [mm] $0^n 1^n$ [/mm] Pärchen. Ist dann das [mm] $1^n$ [/mm] der von dir als zweite Hälfte bezeichnete Teil und [mm] $0^n$ [/mm] der von dir als erste Hälfte bezeichnete Teil?
Oder meinst du das so:
Ich glaub ich muss dafür mal eine Zeichnung machen, wie ich mir das vorstelle:
vorgegebene Aufteilung: [mm] $z=\underbrace{0^n}_{=u}\underbrace{1^n}_{=|vwx|\leq n}\underbrace{0^n1^n}_{y}$
[/mm]
nun mit $z'=uv^0wx^0y$ also [mm] $z'=\underbrace{0^n}_{=u}\underbrace{1^n}_{=|v^0wx^0|\leq n}\underbrace{0^n1^n}_{y}$ [/mm] Was ich hier nun nicht verstehe warum du dann schreibst, dass die erste Hälfte von $z'$ auf 0en endet, da doch eigentlich noch $|w|$ 1en vorhanden sein sollten, oder?
> Wegen $|z'|<4n$ hat die zweite Hälfte von $|z'|$ weniger als $2n$ Buchstaben.). Also kann $z'$ nicht in $L$ liegen.
Da das Wort $z'$ nach "unten gepumpt" worden ist, ist nun $|z'|<4n$, oder? Wieso hat nun die zweite Hälfte von $|z'|$ weniger als $2n$ Buchstaben? Dort wurde doch gar nix verändert, sondern das Wort so gelassen wie es ist, weil ja die zweite Hälft das y ist an dem doch gar nix gedreht wurde, oder?
Ich will mich dann mal am analogen Fall 2 dran machen:
2. Fall: "vwx liegt in der zweiten Hälfte von z"
Dann muss u auf [mm] $0^n 1^n$ [/mm] enden: [mm] $z=\underbrace{0^n1^n}_{=u}\underbrace{0^n}_{=|vwx|\leq n}\underbrace{1^n}_{y}$
[/mm]
angenommen $z'=uv^0wx^0y [mm] \in [/mm] L$: u besteht dann aus der erste Hälfte des Wortes $z'$ [mm] $0^n 1^n$ [/mm] und endet auf [mm] $1^n$.
[/mm]
Somit endet die zweite Hälfte (y) von $z'$ auf [mm] $1^n$. [/mm] Wegen jetzt wieder $z'<4n$ hat die erste Hälfte von $z'$ weniger als 2n Buchstaben. Das ist jetzt nur abgeschrieben weil's wohl richtig ist. Es gilt aber hier nun die gleiche Frage wie ein Stück weiter drüber!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 04:04 Do 16.05.2013 | | Autor: | tobit09 |
> > Somit endet die zweite Hälfte von [mm]z'[/mm] auf 1 und die erste
> Hälfte von [mm]z'[/mm] auf 0 (für Letzteres beachte:
Wir sind also gerade im Fall, dass $vwx$ komplett in der ersten Hälfte von $z$ "liegt".
> Was meinst du mit zweiter Hälfte von [mm]z'[/mm]?
(Nach Annahme (die wir gerade zu widerlegen versuchen), dass $z=uvwxy$ eine Zerlegung mit den Eigenschaften aus dem PL ist, gilt [mm] $z'\in [/mm] L$. Also hat $z'$ die Form $z'=aa$. Insbesondere hat $z'$ eine gerade Anzahl von Buchstaben.)
Wenn [mm] $z'=z'_1z'_2\ldots [/mm] z'_{2k}$ gilt, so meine ich mit der ersten Hälfte von $z'$ das Wort [mm] $z_1'z_2'\ldots [/mm] z'_k$ und mit der zweiten Hälfte das Wort [mm] $z'_{k+1}\ldots [/mm] z'_{2k}$.
> Das y besteht ja
> hier nun aus dem letzten [mm]0^n 1^n[/mm] Pärchen.
y besteht mindestens aus [mm] $0^n1^n$. [/mm] y kann durchaus mit weiteren Buchstaben aus der ersten Hälfte von z beginnen.
> Ist dann das [mm]1^n[/mm]
> der von dir als zweite Hälfte bezeichnete Teil und [mm]0^n[/mm] der
> von dir als erste Hälfte bezeichnete Teil?
Nein.
> Oder meinst du das so:
>
> Ich glaub ich muss dafür mal eine Zeichnung machen, wie
> ich mir das vorstelle:
>
> vorgegebene Aufteilung:
> [mm]z=\underbrace{0^n}_{=u}\underbrace{1^n}_{=|vwx|\leq n}\underbrace{0^n1^n}_{y}[/mm]
Das ist eine mögliche Aufteilung, bei der $vwx$ in der ersten Hälfte von z "liegt". Es gibt aber noch viel mehr solcher Aufteilungen. (Denk daran: Nicht selbst die Aufteilung wählen!)
> nun mit [mm]z'=uv^0wx^0y[/mm] also
> [mm]z'=\underbrace{0^n}_{=u}\underbrace{1^n}_{=|v^0wx^0|\leq n}\underbrace{0^n1^n}_{y}[/mm]
Es gilt doch nicht $z'=z$!
> Was ich hier nun nicht verstehe warum du dann schreibst,
> dass die erste Hälfte von [mm]z'[/mm] auf 0en endet, da doch
> eigentlich noch [mm]|w|[/mm] 1en vorhanden sein sollten, oder?
|w| 1en sind (im Spezialfall deiner Aufteilung) noch vorhanden. Aber $|w|<|n|$. Somit gehört ein Teil der nachfolgenden 0en noch zur ersten Hälfte.
> > Wegen [mm]|z'|<4n[/mm] hat die zweite Hälfte von [mm]|z'|[/mm] weniger als
> [mm]2n[/mm] Buchstaben.). Also kann [mm]z'[/mm] nicht in [mm]L[/mm] liegen.
>
> Da das Wort [mm]z'[/mm] nach "unten gepumpt" worden ist, ist nun
> [mm]|z'|<4n[/mm], oder?
Ja, gegenüber z fehlen in z' die Buchstaben von v und x. Und da [mm] $|vx|\ge [/mm] 1$ fehlt somit mindestens ein Buchstabe. Also besteht z' aus weniger Buchstaben als z. Und z hat genau 4n Buchstaben.
> Wieso hat nun die zweite Hälfte von [mm]|z'|[/mm]
> weniger als [mm]2n[/mm] Buchstaben? Dort wurde doch gar nix
> verändert, sondern das Wort so gelassen wie es ist, weil
> ja die zweite Hälft das y ist an dem doch gar nix gedreht
> wurde, oder?
Die zweite Hälfte von z' stimmt nicht mit der zweiten Hälfte von z überein, da z' insgesamt weniger Buchstaben als z hat und somit auch die beiden Hälften weniger Buchstaben.
Beachte: Mit den beiden Hälften meine ich nicht eine von dir gewählte Zerlegung in zwei Teile, sondern den Anfangs- und den Endteil, die gleich viele Buchstaben haben.
> Ich will mich dann mal am analogen Fall 2 dran machen:
>
> 2. Fall: "vwx liegt in der zweiten Hälfte von z"
>
> Dann muss u auf [mm]0^n 1^n[/mm] enden:
Nein. Aber $u$ muss damit beginnen.
> [mm]z=\underbrace{0^n1^n}_{=u}\underbrace{0^n}_{=|vwx|\leq n}\underbrace{1^n}_{y}[/mm]
Du betrachtest wieder nur einen Spezialfall.
> angenommen [mm]z'=uv^0wx^0y \in L[/mm]: u besteht dann aus der erste
> Hälfte des Wortes [mm]z'[/mm] [mm]0^n 1^n[/mm] und endet auf [mm]1^n[/mm].
Die erste Hälfte von $z'$ endet auf weniger als n 1en.
> Somit endet die zweite Hälfte (y) von [mm]z'[/mm] auf [mm]1^n[/mm].
Die zweite Hälfte von z' endet auf y, aber muss nicht mit y übereinstimmen.
> Wegen
> jetzt wieder [mm]z'<4n[/mm] hat die erste Hälfte von [mm]z'[/mm] weniger als
> 2n Buchstaben.
Das stimmt.
Die erste Hälfte von $z'$ beginnt mit einer 0, die zweite Hälfte von z' mit einer 1. Also [mm] $z'\notin [/mm] L$.
|
|
|
|
