Pumping Lemma Beweis < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | 1.
Sei $w [mm] \in \{0,1\}^{\*}$, [/mm] dann bezeichnet [mm] \overline{w} [/mm] das Wort, das man erhält wenn man in $w$ alle 0 in 1 ersetzt (und umgekehrt). Bsp. [mm] \overline{100} [/mm] = 011.
Zeigen Sie mit Hilfe des Pumping-Lemmas, dass die Sprache $L = [mm] \{w\overline{w} ~ | ~ w \in \{0,1\}^{\*}\}$ [/mm] nicht regulär ist. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Moin,
ich habe eine Frage in Bezug zum Beweis mit Hilfe des Pumping-Lemmas.
Würde die Aufgabe lauten: Zeigen sie mit Hilfe des Pumping-Lemmas, dass die Sprache $L = [mm] \{a^nb^n|n\in\IN_0\}$ [/mm] nicht regulär ist, hätte ich kein Problem damit und könnte den Beweis dafür ohne weiteres aufschreiben.
Hier in diesem Fall komme ich mit der Aufgabe nicht ganz klar.
Ich weiß, dass mein $w [mm] \in \{0,1\}^{\*}$ [/mm] ist, soweit so gut.
Wenn ich nun beweisen möchte, dass die Sprache nicht regulär ist, ist es mir dann erlaubt dies einfach an einem frei gewählten Beispiel für $w$ zu zeigen? Also dürfte ich einfach annehmen, dass beispielsweise für $w = [mm] 0^a1^b$ [/mm] gelte und somit für [mm] $w\overline{w} [/mm] = [mm] 0^a1^b1^a0^b$?
[/mm]
Falls dem so ist, würde ich meinen Beweis wie folgt führen:
Sei $w = [mm] 0^a1^b \Rightarrow$ $w\overline{w} [/mm] = [mm] 0^a1^b1^a0^b \in [/mm] L$
Angenommen $L$ ist regulär, dann gibt es ein $n [mm] \in \IN_0$, [/mm] sodass $z = [mm] 0^n1^b1^n0^b$, [/mm] mit $|z| [mm] \geq [/mm] n$ gilt. Sei $z = tuv$ mit $|tu| [mm] \leq [/mm] n$ und $|u| [mm] \geq [/mm] 1$. Sei $tu = [mm] 0^n$, [/mm] $u = 0$ und $v = [mm] 1^b1^n0^m$.
[/mm]
Dann müsste auch $tu^0v [mm] \in [/mm] L$ gelten, aber $tu^0v = [mm] 0^{n-1}1^b1^n0^b \not\in [/mm] L$, da es mehr 1 in [mm] \overline{w} [/mm] gibt, als es in $w$ 0 gab, also $|w| < [mm] |\overline{w}|$ [/mm] gilt.
Somit ist die Sprache $L$ nicht regulär.
-----------------------
Allerdings sieht das für mich total falsch aus.
Sofern man den Beweis nicht an einem Beispiel führen darf, bitte ich um einen Tipp, wie ich an diese Aufgabe besser herangehen könnte.
Ich bedanke mich schonmal im Voraus.
MfG
Der Pirarrrt
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Di 17.04.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
