Palindrome nicht regulär < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 12:59 Do 03.02.2011 | | Autor: | Scharii |
| Aufgabe | | Zeigen sie dass die Sprache der Palindrome über [mm] ${\lbrace 0,1 \rbrace}^\* [/mm] nicht von einem endlichen deterministischen Automaten erkannt werden kann. |
Hi,
Ich hab ein Problem bei oben stehender Aufgabe.
Ich müsste es mittels Pumping Lemma beweisen, aber ich komm auf keinen grünen Zweig.
Mein Problem ist, im Skript steht das Pumping Lemma:
[mm] w\in [/mm] L(A) mit [mm] |w|\geq [/mm] n lässt sich zerlegen in $w=xyz$ mit
(1) [mm] y\neq\epsilon
[/mm]
(2) [mm] $\forall k\qeq0 [/mm] : xy^kz [mm] \in [/mm] L(A)$
In anderen Büchern, Skripts etc. ist gefordert dass $|xy| [mm] \leq [/mm] n$, aber hier eben nicht.
Ist meine Form "schwächer"? Oder ganz falsch?
Oder, falls nicht, wie kann ich dass so beweisen, ich find nämlich passende Zerlegungen sodass die 2. Bedingung gilt:
$w= [mm] a_1 [/mm] ... [mm] a_n a_n [/mm] ... [mm] a_1$
[/mm]
Wähle $y = w$
Dann ist $x,z = [mm] \epsilon$
[/mm]
Dann ist [mm] $y^k \in [/mm] L(A) [mm] \forall k\geq0$
[/mm]
(Mit der Annahme dass [mm] \epsilon [/mm] ein Palindrom ist)
Hoffe ihr könnt mir weiterhelfen...
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:36 Do 03.02.2011 | | Autor: | felixf |
Moin!
> Zeigen sie dass die Sprache der Palindrome über [mm]${\lbrace 0,1 \rbrace}^\*[/mm]
> nicht von einem endlichen deterministischen Automaten
> erkannt werden kann.
> Hi,
> Ich hab ein Problem bei oben stehender Aufgabe.
> Ich müsste es mittels Pumping Lemma beweisen, aber ich
> komm auf keinen grünen Zweig.
>
> Mein Problem ist, im Skript steht das Pumping Lemma:
> [mm]w\in[/mm] L(A) mit [mm]|w|\geq[/mm] n lässt sich zerlegen in [mm]w=xyz[/mm] mit
> (1) [mm]y\neq\epsilon[/mm]
> (2) [mm]\forall k\qeq0 : xy^kz \in L(A)[/mm]
>
> In anderen Büchern, Skripts etc. ist gefordert dass [mm]|xy| \leq n[/mm],
> aber hier eben nicht.
> Ist meine Form "schwächer"? Oder ganz falsch?
"Falsch" ist es nicht, nur wenig hilfreich 
Die Aussage ist naemlich schwaecher als die des "eigentlichen" Pumping-Lemmas (wie es z.B. in der Wikipedia steht). Die Palindromsprache ist schonmal ein Gegenbeispiel: unten zeigst du ja, dass sie die Aussage des abgeschwaechten Pumpinglemmas erfuellt; die Aussagen des "eigentlichen" PLs erfuellt es dagegen nicht.
> Oder, falls nicht, wie kann ich dass so beweisen,
Mit eurem Pumping-Lemma kannst du es nicht beweisen, wie du schon richtig bemerkst:
> ich find nämlich passende Zerlegungen sodass die 2. Bedingung gilt:
>
> [mm]w= a_1 ... a_n a_n ... a_1[/mm]
> Wähle [mm]y = w[/mm]
> Dann ist [mm]x,z = \epsilon[/mm]
> Dann ist [mm]y^k \in L(A) \forall k\geq0[/mm]
>
> (Mit der Annahme dass [mm]\epsilon[/mm] ein Palindrom ist)
Ich vermute, euer Dozent hat schlichtweg den Teil mit $|x y| [mm] \le [/mm] n$ in der Aussage des PLs vergessen. Frag doch mal euren Dozenten oder Uebungsleiter dazu. Ich waer sehr gespannt was die dazu sagen :)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 20:21 Do 03.02.2011 | | Autor: | Scharii |
Hab in einer Übungsaufgabe(Beweis des PL) das ganze nochmal stehen, so wie ichs im Skript habe, ist also soweit wohl richtig.
Das PL ist von diesem Semester, die Aufgabe oben von einem vorigen Semester(Klausuraufgabe), gleicher Dozent.
Andere Möglichkeit die ich dann hier nur sehe (da das "stärkere" PL nicht eingeführt wurde) wäre über Myhill-Nerode.
Da müsste ja die Anzahl der Äquivalenzklassen der Sprache (bzw. der Relation) unendlich sein.
Da bin ich aber nicht so sicher drin.
Es müsste gelten: Für kein Wort $u$ ausser $w$ und [mm] $w^r$ [/mm] gilt $w [mm] \sim_{R_L} [/mm] u$
Nehm ich mir $w = [mm] a_1 \cdot a_n$ [/mm] und $u = [mm] b_1 \cdot b_n$, [/mm] und hänge ein beliebiges Wort [mm] $q\in A^\*$ [/mm] an.
Dann muss ich aufzeigen, dass [mm] $b_i [/mm] = [mm] a_i \forall [/mm] i [mm] \in \lbrace 0...n\rbrace$.
[/mm]
Wie mach ich das? ich müsste ja das ganze mit den Buchstaben von q vergleichen, aber ich krieg das grad nicht intuitiv hin.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:21 Sa 05.02.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:21 Sa 05.02.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
