Pumping Lemma < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:10 Di 30.04.2013 | | Autor: | bandchef |
| Aufgabe | Ist die Sprache regulär?
[mm] $L=\{ a^i b^k a^k | i,k\in \mathbb N_0 \} \cup \{b^ia^k|i,k\in \mathbb N_0\}$ [/mm] |
Hi Leute!
Ich hab mir gedacht, dass ich hier wohl über die Abschlusseigenschaft argumentieren muss. Ich teile die Sprache in zwei Teilsprachen auf und da man weiß, dass die Vereinigung von zwei regulären Sprachen wieder regulär ist, müssen so für die gesamte Sprache L beide Teilsprachen regulär sein:
Es gilt das PL: Die Definition schreib ich nicht schon wieder rein. Deswegen gleich zum interessanten Teil:
[mm] $L=\underbrace{\{ a^i b^k a^k | i,k\in \mathbb N_0 \}}_{:=L_2} \cup \underbrace{\{b^ia^k|i,k\in \mathbb N_0\}}_{:=L_3}$
[/mm]
Beweis für [mm] $L_2$:
[/mm]
[mm] $z_2 [/mm] = [mm] \underbrace{a^n}_{u} \underbrace{b^{2n}}_{v} \underbrace{a^{2n}}_{w}$ [/mm] außerdem: $n+2n+2n = 5n [mm] \geq [/mm] n$
Wenn ich nun in v auf oder abpumpe bekomm ich ein anderes k und die Sprache fliegt raus und es gilt: $uv^0w [mm] \notin [/mm] L$
Beweis: für [mm] $L_3§$:
[/mm]
[mm] $z_3 [/mm] = [mm] b^n a^n [/mm] = [mm] \underbrace{b^n}_{uv} \underbrace{a^n}_{w}$ [/mm] außerdem: [mm] $n+n=2n\geq [/mm] n$
Wenn ich nun in v auf oder abpumpe bekomm ich zwar ein größere/kleinere Anzahl a's aber es bleibt dennoch in der Sprache weil ich laut Sprachdefinition ja unterschiedlich viele a's erlaubt sind! Es gilt also: $uv^0w [mm] \in [/mm] L$.
Laut Abschlusseigenschaft für Vereinigung ist die gesamte Sprache L so nicht regulär, da dafür beide Teile regulär sin müssten!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:23 Di 30.04.2013 | | Autor: | tobit09 |
Hallo bandchef,
> [mm]L=\{ a^i b^k a^k | i,k\in \mathbb N_0 \} \cup \{b^ia^k|i,k\in \mathbb N_0\}[/mm]
> Ich hab mir gedacht, dass ich hier wohl über die
> Abschlusseigenschaft argumentieren muss. Ich teile die
> Sprache in zwei Teilsprachen auf und da man weiß, dass die
> Vereinigung von zwei regulären Sprachen wieder regulär
> ist, müssen so für die gesamte Sprache L beide
> Teilsprachen regulär sein:
Letzteres stimmt nicht. WENN [mm] $L_1$ [/mm] und [mm] $L_2$ [/mm] regulär sind, so ist auch [mm] $L_1\cup L_2$ [/mm] regulär. Wenn du dagegen nur weißt, das [mm] $L_1\cup L_2$ [/mm] regulär ist, weißt du nicht, ob auch [mm] $L_1$ [/mm] und [mm] $L_2$ [/mm] regulär sind.
> Es gilt das PL: Die Definition schreib ich nicht schon
> wieder rein. Deswegen gleich zum interessanten Teil:
>
> [mm]L=\underbrace{\{ a^i b^k a^k | i,k\in \mathbb N_0 \}}_{:=L_2} \cup \underbrace{\{b^ia^k|i,k\in \mathbb N_0\}}_{:=L_3}[/mm]
>
>
>
> Beweis für [mm]L_2[/mm]:
Du möchtest also zeigen, dass [mm] $L_2$ [/mm] nicht regulär ist.
Spare im Ernstfall (Klausur) nicht an den erläuternden Worten!
> [mm]z_2 = \underbrace{a^n}_{u} \underbrace{b^{2n}}_{v} \underbrace{a^{2n}}_{w}[/mm]
> außerdem: [mm]n+2n+2n = 5n \geq n[/mm]
Du darfst $u$, $v$ und $w$ nicht selbst wählen! Diese Zerlegung liefert dir das Pumping Lemma aus der Widerspruchsannahme, dass [mm] $L_2$ [/mm] regulär wäre.
> Wenn ich nun in v auf oder abpumpe bekomm ich ein anderes k
> und die Sprache fliegt raus und es gilt: [mm]uv^0w \notin L[/mm]
> Beweis: für [mm]L_3§[/mm]:
Was möchtest du eigentlich hier beweisen? Offenbar, dass die Bedingung aus dem Pumping Lemma erfüllt ist. Daraus folgt noch nicht, dass [mm] $L_3$ [/mm] regulär ist. (Auch wenn [mm] $L_3$ [/mm] hier tatsächlich regulär ist.)
Um zu zeigen, dass die Bedingung aus dem Pumping Lemma erfüllt ist, müsstest du eine Zahl $n$ mit der Eigenschaft aus dem Pumping Lemma angeben (und nachweisen, dass $n$ tatsächlich diese Eigenschaft hat).
> [mm]z_3 = b^n a^n = \underbrace{b^n}_{uv} \underbrace{a^n}_{w}[/mm]
> außerdem: [mm]n+n=2n\geq n[/mm]
>
> Wenn ich nun in v auf oder abpumpe bekomm ich zwar ein
> größere/kleinere Anzahl a's aber es bleibt dennoch in der
> Sprache weil ich laut Sprachdefinition ja unterschiedlich
> viele a's erlaubt sind! Es gilt also: [mm]uv^0w \in L[/mm].
> Laut Abschlusseigenschaft für Vereinigung ist die gesamte
> Sprache L so nicht regulär, da dafür beide Teile regulär
> sin müssten!
Dies kannst du so nicht folgern (s.o.).
Viele Grüße
Tobias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:38 Mi 01.05.2013 | | Autor: | bandchef |
Du darfst $u$, $v$ und $w$ nicht selbst wählen!
Das ist mein Hauptproblem bei solchen Aufgaben! Wie sieht das dann richtig aus? Was muss ich machen, dass u,v und w nicht selbst wähle??? Ich kapier das einfach nicht :-(
Diese Zerlegung liefert dir das Pumping Lemma aus der Widerspruchsannahme, dass [mm] $L_2$ [/mm] regulär wäre.
Wie geht das? Was muss ich hierzu machen? Ich hab grad auch irgendwie nicht mehr den Durchblick wie ich eine Widerspruchsannahme machen muss! Ich hab eine Sprache (hier eine Teilsprache gegeben) an der ich mit dem PL zeigen will, dass sie nicht regulär ist! Quasi, dass das PL ein Wort findet, das nicht in der Sprache liegt, oder? Wenn das PL so ein Wort findet ist meine Teilsprache nicht mehr regulär und somit kann auch die gesamte Sprache nicht mehr regulär sein! Stimmt das so?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:58 Do 02.05.2013 | | Autor: | tobit09 |
> Du darfst [mm]u[/mm], [mm]v[/mm] und [mm]w[/mm] nicht selbst wählen!
>
> Das ist mein Hauptproblem bei solchen Aufgaben! Wie sieht
> das dann richtig aus? Was muss ich machen, dass u,v und w
> nicht selbst wähle??? Ich kapier das einfach nicht :-(
Angenommen $L$ wäre regulär.
Nach Pumping Lemma existiert dann ein [mm] $n\in\IN$ [/mm] mit folgender Eigenschaft: Für alle [mm] $z\in [/mm] L$ mit [mm] $|z|\ge [/mm] n$ existiert eine Aufteilung $z=uvw$ mit: [mm] $|uv|\le [/mm] n$, [mm] $|v|\ge1$ [/mm] und [mm] $uv^iw\in [/mm] L$ für alle [mm] $i\in\IN_0$.
[/mm]
Habe also $n$ diese Eigenschaft.
Insbesondere existiert eine Aufteilung $z=uvw$ mit den genannten Eigenschaften für [mm] $z:=\ldots$ [/mm] (denn [mm] $z\in [/mm] L$ und [mm] $|z|\ge [/mm] n$).
blablabla
Also liegt $uv^0w$ (oder $uv^2w$ oder [mm] $uv^{9457345}w$) [/mm] nicht in $L$ im Widerspruch zur Wahl der Zerlegung $z=uvw$.
Also war die Annahme, dass $L$ regulär sei, falsch.
> Diese Zerlegung liefert dir das Pumping Lemma aus der
> Widerspruchsannahme, dass [mm]L_2[/mm] regulär wäre.
>
> Wie geht das? Was muss ich hierzu machen? Ich hab grad auch
> irgendwie nicht mehr den Durchblick wie ich eine
> Widerspruchsannahme machen muss!
s.o.
> Ich hab eine Sprache (hier
> eine Teilsprache gegeben) an der ich mit dem PL zeigen
> will, dass sie nicht regulär ist! Quasi, dass das PL ein
> Wort findet, das nicht in der Sprache liegt, oder?
So ganz kann ich dir hier nicht folgen.
> Wenn das
> PL so ein Wort findet ist meine Teilsprache nicht mehr
> regulär und somit kann auch die gesamte Sprache nicht mehr
> regulär sein! Stimmt das so?
Nein. Wie ich in der vorherigen Antwort schrieb: Wenn eine Teilsprache nicht regulär ist, heißt das noch lange nicht, dass die gesamte Sprache nicht regulär ist.
Übrigens ist die hier vorliegende Sprache ein Beispiel für eine nichtreguläre Sprache, die der Bedingung aus dem Pumping Lemma trotzdem genügt (sogar mit $n=1$).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:59 So 05.05.2013 | | Autor: | bandchef |
> Übrigens ist die hier vorliegende Sprache ein Beispiel für eine nichtreguläre Sprache, die > der Bedingung aus dem Pumping Lemma trotzdem genügt (sogar mit ).
Genau das hat unser Prof. letztens auch gemeint.
Ich würde das aber gerne jetzt selber mal sehen... Ich weiß nur immer noch nicht wie ich da anfangen soll; ich probier's aber jetzt trotzdem mal:
Sei [mm] $L_2$ [/mm] eine reguläre Sprache, dann gibt es eine Konstante $n [mm] \in \mathbb [/mm] N$, so dass sich jedes $z [mm] \in [/mm] L$ mit [mm] $|z|\geq [/mm] n$, so als z=uvw schreiben lässt, dass [mm] $|uv|\leq [/mm] n$, [mm] $|v|\geq [/mm] 1$ und $u [mm] v^i [/mm] w [mm] \in [/mm] L$ für alle $i [mm] \geq [/mm] 0$ gilt:
Ich wähle nun ein Wort z in Abhängigkeit der Sprache [mm] $L_2$ [/mm] mit [mm] $|z|\geq [/mm] n$:
$z = [mm] a^n b^{2n} a^{2n}$ $\Rightarrow [/mm] |z| = n+2n+2n = 5n [mm] \geq [/mm] n$ (die erste Bedingung des PL sollte doch hiermit erfüllt sein, oder?)
Soweit richtig?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:38 So 05.05.2013 | | Autor: | tobit09 |
> > Übrigens ist die hier vorliegende Sprache ein Beispiel
> für eine nichtreguläre Sprache, die > der Bedingung aus
> dem Pumping Lemma trotzdem genügt (sogar mit ).
>
> Genau das hat unser Prof. letztens auch gemeint.
Nur um eventuelle Missverständnisse auszuräumen: Ich meinte hier die Sprache $L$, nicht die Sprache [mm] $L_2$.
[/mm]
> Ich würde das aber gerne jetzt selber mal sehen... Ich
> weiß nur immer noch nicht wie ich da anfangen soll; ich
> probier's aber jetzt trotzdem mal:
>
>
>
>
> Sei [mm]L_2[/mm] eine reguläre 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=uvw schreiben lässt, dass [mm]|uv|\leq n[/mm], [mm]|v|\geq 1[/mm]
> und [mm]u v^i w \in L[/mm] für alle [mm]i \geq 0[/mm] gilt:
Nun möchtest du also nicht ANNEHMEN, dass die Bedingung aus dem Pumping Lemma gilt, und dies zum Widerspruch führen, sondern ZEIGEN, dass die Bedingung aus dem Pumping Lemma gilt.
Du möchtest also nun zeigen, dass ein [mm] $n\in\IN$ [/mm] mit einer gewissen Eigenschaft existiert.
Gib dazu ein Beispiel für ein solches $n$ an und zeige, dass es dieses $n$ tut. Ich habe dir schon verraten, dass du $n=1$ nehmen kannst.
Zu zeigen ist nun, dass für alle [mm] $z\in [/mm] L$ mit [mm] $|z|\ge [/mm] 1$ eine Zerlegung $z=uvw$ mit gewissen Eigenschaften existiert.
Dazu darfst du nicht selbst ein Wort [mm] $z\in [/mm] L$ wählen, sondern musst ein beliebig vorgegebenes Wort [mm] $z\in [/mm] L$ der Länge [mm] $\ge1$ [/mm] "entgegennehmen" und zeigen, dass dieses Wort $z$ eine Zerlegung $z=uvw$ mit den gewünschten Eigenschaften besitzt. (Da [mm] $z\in [/mm] L$ mit [mm] $|z|\ge1$ [/mm] beliebig vorgegeben war, gilt die Existenz einer solchen Zerlegung dann für ALLE [mm] $z\in [/mm] L$ mit [mm] $|z|\ge1$.)
[/mm]
Das einzige, was du über $z$ weißt, ist [mm] $z\in [/mm] L$ (d.h. ?) und [mm] $|z|\ge [/mm] 1$ (d.h. $z$ ist nicht das leere Wort).
> Ich wähle nun ein Wort z in Abhängigkeit der Sprache [mm]L_2[/mm]
> mit [mm]|z|\geq n[/mm]:
Nein, nicht selbst wählen (s.o.).
> [mm]z = a^n b^{2n} a^{2n}[/mm] [mm]\Rightarrow |z| = n+2n+2n = 5n \geq n[/mm]
> (die erste Bedingung des PL sollte doch hiermit erfüllt
> sein, oder?)
Was meinst du mit der "ersten Bedingung des PL"?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:46 So 05.05.2013 | | Autor: | bandchef |
> Dazu darfst du nicht selbst ein Wort [mm] $z\in [/mm] L$ wählen, sondern musst ein beliebig
> vorgegebenes Wort [mm] $z\in [/mm] L$ der Länge [mm] $\ge1$ [/mm] "entgegennehmen" und zeigen, dass
> dieses Wort $z$ eine Zerlegung $z=uvw$ mit den gewünschten Eigenschaften besitzt.
Von wo soll ich denn das beliebige Wort entgegennehmen mir ist ja nix gegeben...? Ich habe eigentlich gedacht, dass ich mit meinem Wort $z = [mm] a^n b^{2n} a^{2n}$ [/mm] beliebig genug bin! Wo ist dann hier schon wieder der Fehler?
> Nein, nicht selbst wählen (s.o.).
Wenn mein Lösungsvorschlag falsch war, wie muss ich es dann machen? In bisherigen Übungsaufgaben die unser Prof. mit uns gelöst hat, und deren Aufbau der Sprache ähnlich war, hat er das aber auch immer so gemacht. Er hat immer versucht, die Sprache und evtl. Potenzen von n abhängig zu machen und hat dann meist eine kleine Ungleichung als Abschätzung angeführt. Kann man das hier nicht so machen?
> Was meinst du mit der "ersten Bedingung des PL"?
Unter erster Bedingung des PL's verstehe ich, dass eben das Wort z die Eigenschaft $|z| [mm] \geq [/mm] 1$ besitzen muss.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:43 So 05.05.2013 | | Autor: | tobit09 |
> > Dazu darfst du nicht selbst ein Wort [mm]z\in L[/mm] wählen,
> sondern musst ein beliebig
> > vorgegebenes Wort [mm]z\in L[/mm] der Länge [mm]\ge1[/mm]
> "entgegennehmen" und zeigen, dass
> > dieses Wort [mm]z[/mm] eine Zerlegung [mm]z=uvw[/mm] mit den gewünschten
> Eigenschaften besitzt.
>
> Von wo soll ich denn das beliebige Wort entgegennehmen mir
> ist ja nix gegeben...?
Naja, zumindest [mm] $z\in [/mm] L$ und [mm] $|z|\ge [/mm] 1$ ist dir gegeben.
> Ich habe eigentlich gedacht, dass
> ich mit meinem Wort [mm]z = a^n b^{2n} a^{2n}[/mm] beliebig genug
> bin! Wo ist dann hier schon wieder der Fehler?
Du willst eine Aussage über ALLE Wörter aus $L$ der Länge [mm] $\ge [/mm] 1$ beweisen, nicht nur über Wörter der Form [mm] $z=a^nb^{2n}a^{2n}$.
[/mm]
> > Nein, nicht selbst wählen (s.o.).
>
> Wenn mein Lösungsvorschlag falsch war, wie muss ich es
> dann machen? In bisherigen Übungsaufgaben die unser Prof.
> mit uns gelöst hat, und deren Aufbau der Sprache ähnlich
> war, hat er das aber auch immer so gemacht. Er hat immer
> versucht, die Sprache und evtl. Potenzen von n abhängig zu
> machen und hat dann meist eine kleine Ungleichung als
> Abschätzung angeführt. Kann man das hier nicht so
> machen?
Wahrscheinlich hat der Prof. auch stets ANGENOMMEN, dass die Bedingung aus dem Pumping Lemma gelte, und dies zum Widerspruch geführt. Jetzt möchtest du aber ZEIGEN, dass die Bedingung aus dem Pumping Lemma gilt.
Was zu tun ist, habe ich ja im vorherigen Beitrag geschrieben. Was bedeutet denn [mm] $z\in [/mm] L$? Welche Formen kann $z$ also haben?
Finde dann jeweils eine geeignete Zerlegung $z=uvw$, so dass [mm] $|uv|\le [/mm] 1$, [mm] $|v|\ge [/mm] 1$ (damit hast du schon nicht mehr viel Auswahlmöglichkeit für die Zerlegung...) und [mm] $uv^iw\in [/mm] L$ für alle [mm] $i\in\IN_0$.
[/mm]
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:56 Mo 06.05.2013 | | Autor: | bandchef |
> Wahrscheinlich hat der Prof. auch stets ANGENOMMEN, dass die Bedingung aus dem
> Pumping Lemma gelte, und dies zum Widerspruch geführt. Jetzt möchtest du aber
> ZEIGEN, dass die Bedingung aus dem Pumping Lemma gilt.
Ja, genau das hat er gemacht. Aber: Will ich das nun bei dieser Aufgabe nicht auch so machen? Ich will doch immer versuchen, zu widerlegen dass die Sprache nicht regulär ist, weswegen ich ja auch annehme, dass die Sprache regulär sei, oder?
Ich hatte immer gedacht, dass ich mit dem PL gar nicht so richtig zeigen kann, dass eine Sprache regulär ist, oder? Und genau das willst du ja jetzt mit dem PL machen, nämlich zeigen, DASS die Sprache regulär ist...
Nur nochmal zum Verständnis: Mit der Möglichkeit von $ [mm] z=a^nb^{2n}a^{2n} [/mm] $ habe ich ein einziges Wort aus der Sprache genommen und könnte nun anhand diesem Wort zeigen, dass die Sprache nicht regulär ist weil ich das Wort so pumpen könnte, dass das gepumpte Wort nicht mehr in der Sprache liegt weshalb die Sprache nicht regulär sein kann, richtig?
Was ich jetzt nicht verstehe, ist, warum genau dieses Vorgehen nun falsch sein soll...; ich will ja zeigen, dass die gesamte Sprache aus meiner Aufgabe regulär ist bzw. eben nicht. Wenn ich nun für eine Teilsprache (in meinem Fall [mm] L_2) [/mm] zeige, dass sie nicht regulär ist, kann die gesamte Sprache L auch nicht mehr regulär sein, oder?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:28 Di 07.05.2013 | | Autor: | tobit09 |
> > Wahrscheinlich hat der Prof. auch stets ANGENOMMEN, dass
> die Bedingung aus dem
> > Pumping Lemma gelte, und dies zum Widerspruch geführt.
> Jetzt möchtest du aber
> > ZEIGEN, dass die Bedingung aus dem Pumping Lemma gilt.
>
>
> Ja, genau das hat er gemacht. Aber: Will ich das nun bei
> dieser Aufgabe nicht auch so machen? Ich will doch immer
> versuchen, zu widerlegen dass die Sprache nicht regulär
> ist, weswegen ich ja auch annehme, dass die Sprache
> regulär sei, oder?
Das ist in der Tat der übliche Anwendungsfall des Pumping Lemmas.
> Ich hatte immer gedacht, dass ich mit dem PL gar nicht so
> richtig zeigen kann, dass eine Sprache regulär ist, oder?
Richtig.
> Und genau das willst du ja jetzt mit dem PL machen,
> nämlich zeigen, DASS die Sprache regulär ist...
Nein, das will ich nicht. Ich habe dich hier so verstanden, dass du zeigen möchtest, dass die Bedingung aus dem Pumping Lemma für unser $L$ gilt. Über die Regularität von $L$ sagt das natürlich nichts aus.
> Was ich jetzt nicht verstehe, ist, warum genau dieses
> Vorgehen nun falsch sein soll...; ich will ja zeigen, dass
> die gesamte Sprache aus meiner Aufgabe regulär ist bzw.
> eben nicht.
OK, dann habe ich dich missverstanden.
> Wenn ich nun für eine Teilsprache (in meinem
> Fall [mm]L_2)[/mm] zeige, dass sie nicht regulär ist, kann die
> gesamte Sprache L auch nicht mehr regulär sein, oder?
Diese Schlussfolgerung ist falsch! Zum dritten Mal: Wenn [mm] $L_2$ [/mm] nicht regulär ist, kann a priori [mm] $L=L_2\cup L_3$ [/mm] sehr wohl regulär sein!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:21 Di 07.05.2013 | | Autor: | bandchef |
> Diese Schlussfolgerung ist falsch! Zum dritten Mal: Wenn [mm] $L_2$ [/mm] nicht regulär ist, kann a
> priori [mm] $L=L_2\cup L_3$ [/mm] sehr wohl regulär sein!
Da hast du Recht. Ich hab mir das jetzt so notiert:
L ist nicht regulär. Die Teilsprache [mm] L_3 [/mm] ist regulär, weil ich einen DEA zeichnen könnte. Die Sprache [mm] L_2 [/mm] ist nicht regulär. Laut Abschlusseigenschaft für Vereinigung müssen aber beide Teilsprachen regulär sein, damit die ganze Sprache L regulär wäre.
Man kann aber mit dem PL zeigen, dass die gesamte Sprache L regulär ist, weil man das PL auf Teilsprache [mm] L_2 [/mm] so anwenden könnte (Zum zeigen! Nicht zum widerlegen!), dass die Sprache [mm] L_2 [/mm] Wörter "generiert", die eine Teilmenge von [mm] L_3 [/mm] darstellen und somit regulär werden. Die gesamte Sprache ist aber dann noch lange nicht regulär.
Hab ich das jetzt richtig erklärt?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 04:57 Mi 08.05.2013 | | Autor: | tobit09 |
> L ist nicht regulär.
Was noch unbewiesen ist.
> Die Teilsprache [mm]L_3[/mm] ist regulär,
> weil ich einen DEA zeichnen könnte.
Ja.
> Die Sprache [mm]L_2[/mm] ist
> nicht regulär.
Ja. Kann man mit Pumping Lemma zeigen.
> Laut Abschlusseigenschaft für Vereinigung
> müssen aber beide Teilsprachen regulär sein, damit die
> ganze Sprache L regulär wäre.
Nein! Bitte nimm doch endlich zur Kenntnis, dass dieser Schluss falsch ist!
> Man kann aber mit dem PL zeigen, dass die gesamte Sprache L
> regulär ist,
Nein. Wie du selbst korrekterweise festgestellt hast, kann man mit PL keine Regularität nachweisen. Außerdem ist $L$ nicht regulär.
> weil man das PL auf Teilsprache [mm]L_2[/mm] so
> anwenden könnte (Zum zeigen! Nicht zum widerlegen!)
Was möchtest du zeigen?
> dass
> die Sprache [mm]L_2[/mm] Wörter "generiert", die eine Teilmenge von
> [mm]L_3[/mm] darstellen und somit regulär werden.
Was meinst du damit, dass "Wörter regulär werden"?
> Die gesamte
> Sprache ist aber dann noch lange nicht regulär.
Ja, $L$ ist nicht regulär (was wir noch nicht bewiesen haben).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:36 Mi 08.05.2013 | | Autor: | bandchef |
> Nein! Bitte nimm doch endlich zur Kenntnis, dass dieser Schluss falsch ist!
Ok. Es kann also eine Sprache, bestehende aus zwei Teilsprachen, regulär sein, obwohl eine der beiden (oder beide) Teilsprachen nicht regulär ist (sind)?
Ich verstehe dann einfach nicht, wieso in meinem Buch steht, dass die Vereinigung zweier regulärer Sprachen regulär ist. Warum gilt das dann aber hier nicht?
> Nein. Wie du selbst korrekterweise festgestellt hast, kann man mit PL keine Regularität
> nachweisen. Außerdem ist L nicht regulär.
Was kann man mit dem PL denn dann überhaupt? Kann man nur widerlegen? Das PL ist doch eine Implikation, oder? Aber eine Implikation von was zu was= Kann man das nicht irgendwie in einen Satz fassen, den ich auswendig lernen kann um überhaupt irgendwie mal ein Hilfsmittel an der Hand zu haben?
> Was möchtest du zeigen?
Ich möchte zeigen, dass [mm] L_2 [/mm] nicht regulär ist, zu dem sich doch das PL eignet, oder? Ich behaupte, dass [mm] L_2 [/mm] regulär wäre und zeige dann mit dem PL, dass sie es eben nicht ist.
> Was meinst du damit, dass "Wörter regulär werden"?
Die Sprache L ist also nicht regulär (was man aber noch zeigen muss, ja). Ich weiß nun durch den DEA, dass [mm] L_3 [/mm] regulär ist. Ich will nun mit dem PL widerlegen, dass [mm] L_2 [/mm] regulär wäre. Also hab ich nun quasi sowas: L = nicht reguläre Sprache [mm] $\cup$ [/mm] reguläre Sprache. Und da muss ich doch jetzt mit den Abschlusseigenschaften ran. nicht regulär [mm] $\cup$ [/mm] regulär = nicht regulär.
Weißt du jetzt was ich meine?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:26 Do 09.05.2013 | | Autor: | tobit09 |
> Es kann also eine Sprache, bestehende aus zwei
> Teilsprachen, regulär sein, obwohl eine der beiden (oder
> beide) Teilsprachen nicht regulär ist (sind)?
Genau.
> Ich verstehe dann einfach nicht, wieso in meinem Buch
> steht, dass die Vereinigung zweier regulärer Sprachen
> regulär ist. Warum gilt das dann aber hier nicht?
Das gilt auch hier. Wenn [mm] $L_1$ [/mm] und [mm] $L_2$ [/mm] regulär sind, so auch [mm] $L_1\cup L_2$. [/mm] Aber wenn [mm] $L_1$ [/mm] oder [mm] $L_2$ [/mm] nicht regulär sind, wissen wir im Allgemeinen nicht, ob [mm] $L_1\cup L_2$ [/mm] regulär ist.
> > Wie du selbst korrekterweise festgestellt hast, kann
> man mit PL keine Regularität
> > nachweisen. Außerdem ist L nicht regulär.
>
> Was kann man mit dem PL denn dann überhaupt? Kann man nur
> widerlegen?
Genau. Dazu ist das PL häufig die Methode der Wahl.
> Das PL ist doch eine Implikation, oder? Aber
> eine Implikation von was zu was= Kann man das nicht
> irgendwie in einen Satz fassen, den ich auswendig lernen
> kann um überhaupt irgendwie mal ein Hilfsmittel an der
> Hand zu haben?
Das habt ihr doch sicherlich in eurer Mitschrift:
Wenn $L$ eine reguläre Sprache ist, so gibt es ein [mm] $n\in\IN$, [/mm] so dass...
Das Pumping Lemma liefert also die Implikation von der Regularität von $L$ zu der Bedingung, dass ein [mm] $n\in\IN$ [/mm] existiert mit...
> > Was möchtest du zeigen?
>
> Ich möchte zeigen, dass [mm]L_2[/mm] nicht regulär ist, zu dem
> sich doch das PL eignet, oder? Ich behaupte, dass [mm]L_2[/mm]
> regulär wäre und zeige dann mit dem PL, dass sie es eben
> nicht ist.
OK.
> > Was meinst du damit, dass "Wörter regulär werden"?
>
> Die Sprache L ist also nicht regulär (was man aber noch
> zeigen muss, ja). Ich weiß nun durch den DEA, dass [mm]L_3[/mm]
> regulär ist. Ich will nun mit dem PL widerlegen, dass [mm]L_2[/mm]
> regulär wäre. Also hab ich nun quasi sowas: L = nicht
> reguläre Sprache [mm]\cup[/mm] reguläre Sprache. Und da muss ich
> doch jetzt mit den Abschlusseigenschaften ran. nicht
> regulär [mm]\cup[/mm] regulär = nicht regulär.
>
> Weißt du jetzt was ich meine?
Ich weiß, was du meinst, kann dich aber nur immer wieder darauf hinweisen, dass das, was du mit
> nicht regulär [mm]\cup[/mm] regulär = nicht regulär.
beschreibst, falsch ist.
Die Abschlusseigenschaften sagen dir lediglich das, was du wohl mit
"regulär [mm] $\cup$ [/mm] regulär = regulär"
abkürzen würdest.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:15 Mi 27.11.2013 | | Autor: | Xanthi |
Ich habe die gleiche Aufgabe zu lösen, deshalb wollte ich die Diskussion hier nochmal hervorbringen, da es keine Lösung zu dieser Aufgabe gibt und ich kein bisschen weiterkommen.
Die Argumentation usw. ist völlig klar, der entsprechende Beweis ob die Sprache regulär oder nicht regulär ist fehlt jedoch.
Egal wie man es dreht und wendet, ein Pumping-Lemma Ansatz führt hier nicht zum Ziel und die Abschlusseigenschaften ebenfalls nicht.
Nach etwas Überlegun war mein Ansatz für das PL das Beispielwort $z = [mm] ab^na^n$ [/mm] zu wählen. Dies macht aber für $|u| = [mm] \epsilon$ [/mm] und $|v| = 1$ probleme, da Sie nicht aus L rausgepumpt werden kann.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:00 Mo 02.12.2013 | | Autor: | Xanthi |
Danke :)
Habe es letzte Woche mit Jaffe's PL probiert und komme ebenfalls auf kein sinnvolles Ergebnis. Wobei Jaffe's PL ebenfalls äquivalent ist zur Definition von regulären Sprachen ist und eine hinreichende Bedingung liefert. Somit 'müsste' es damit ebenfalls möglich sein.
Habe es dann mit Nerode probiert, mit dem es erstaunlich (zu einfach?) funktioniert. Könntest du diese Lösung kurz überprüfen? :) - Ist in erster herangehensweise sicherlich nicht ganz korrekt, nur Approxximativ
Sei ~_L die Nerode Relation. Es entstehen folgende Äquivalenzklassen :
*edited*
Ich bezeichne die Äquivalenzklassen mit den Suffixen die ich verwende.
Im Endeffekt die drei unrelevanten Klassen für den zweiten Teil der Sprache.
Neben den Äquivalenzklassen die für den regulären Teil der Sprache entstehen, sind die Äquivalenzklassen für den nicht regulären Teil von größeren Interesse.
Dabei Sei [mm] $x_i [/mm] = [mm] a^lb^i, [/mm] l [mm] \in \mathbb{N},i \in \mathbb{N}_0$. [/mm] Dabei gilt jeweils, dass [mm] $x_i \not\equiv [/mm] _{L} [mm] x_j$ [/mm] für $i [mm] \neq [/mm] j$, da für $z = [mm] a^i$ [/mm] gilt:
$x_iz = [mm] a^lb^ia^i \in [/mm] L$, jedoch $x^jz = [mm] a^lb^ja^i$ \notin [/mm] L - Aufgrund von i [mm] \neq [/mm] j.
Daraus folgt jedoch sofort, dass sich unendlich viele disjunkte Äquivalenzklassen bilden und die Sprache nicht regulär ist, nach dem Satz von Myhill-Nerode. Die Äquivalenzklassen sind folgende:
$[a] = [mm] \{a^lb, a^lb^2a,a^lb^3a^2... \}$ [/mm] Suffix a
$[aa] = [mm] \{a^lb^2, a^lb^3a,a^lb^4a^2... \}$ [/mm] Suffix aa
$[aaa] = [mm] \{a^lb^3 ,a^lb^4a,a^lb^5a^2... \}$ [/mm] Suffix aaa
[mm] \vdots [/mm]
Dieses Ergebnis spiegelt Quasi die resultate der oben genannten Argumentation wieder und sollte somit alles korrekt sein.
Die Frage die bleibt, es müsste auch mit Jaffe's PL funktionieren, das ebenfalls eine hinreichende Bedingung liefert. Also "muss" es faktisch möglich sein, jedoch hab ich das nicht hinbekommen - Nerode ist in diesem Fall auf jeden Fall einfach, falls ich keinen Fehler gemacht habe. Dennoch - wie gesagt, ein Tipp zu Jaffe wäre interesannt :)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:29 Di 03.12.2013 | | Autor: | tobit09 |
> Habe es dann mit Nerode probiert, mit dem es erstaunlich
> (zu einfach?) funktioniert. Könntest du diese Lösung kurz
> überprüfen? :) - Ist in erster herangehensweise
> sicherlich nicht ganz korrekt, nur Approxximativ
>
> Sei ~_L die Nerode Relation. Es entstehen folgende
> Äquivalenzklassen :
>
> *edited*
>
> Ich bezeichne die Äquivalenzklassen mit den Suffixen die
> ich verwende.
>
> Im Endeffekt die drei unrelevanten Klassen für den zweiten
> Teil der Sprache.
Was meinst du mit "Klassen für den zweiten Teil der Sprache"?
> Neben den Äquivalenzklassen die für den regulären Teil
> der Sprache entstehen, sind die Äquivalenzklassen für den
> nicht regulären Teil von größeren Interesse.
Was meinst du mit "regulärem" bzw. "nicht regulärem Teil der Sprache"? Was meinst du mit "den Äquivalenzklassen für einen Teil"?
> Dabei Sei [mm]x_i = a^lb^i, l \in \mathbb{N},i \in \mathbb{N}_0[/mm].
> Dabei gilt jeweils, dass [mm]x_i \not\equiv _{L} x_j[/mm] für [mm]i \neq j[/mm],
> da für [mm]z = a^i[/mm] gilt:
> [mm]x_iz = a^lb^ia^i \in L[/mm], jedoch [mm]x^jz = a^lb^ja^i[/mm] [mm]\notin[/mm] L -
> Aufgrund von i [mm]\neq[/mm] j.
Sehr schön! ![[ok]](/images/smileys/ok.gif "[ok]")
> Daraus folgt jedoch sofort, dass sich unendlich viele
> disjunkte Äquivalenzklassen bilden und die Sprache nicht
> regulär ist, nach dem Satz von Myhill-Nerode.
Damit bist du fertig.
> Die
> Äquivalenzklassen sind folgende:
>
> [mm][a] = \{a^lb, a^lb^2a,a^lb^3a^2... \}[/mm] Suffix
> a
> [mm][aa] = \{a^lb^2, a^lb^3a,a^lb^4a^2... \}[/mm] Suffix
> aa
> [mm][aaa] = \{a^lb^3 ,a^lb^4a,a^lb^5a^2... \}[/mm] Suffix
> aaa
> [mm]\vdots[/mm]
(Was meinst du hier mit $l$?)
Nein. Es ist
[mm] $[a]=[aa]=[aaa]=\{a^l\;|\;l\in\IN\setminus\{0\}\}$.
[/mm]
Natürlich gibt es noch weitere Äquivalenzklassen. Aber deren genaue Bestimmung ist zum Nachweis, dass es unendlich viele Äquivalenzklassen gibt, nicht erforderlich.
> Dieses Ergebnis spiegelt Quasi die resultate der oben
> genannten Argumentation wieder
Nein.
> und sollte somit alles
> korrekt sein.
> Habe es letzte Woche mit Jaffe's PL probiert und komme
> ebenfalls auf kein sinnvolles Ergebnis. Wobei Jaffe's PL
> ebenfalls äquivalent ist zur Definition von regulären
> Sprachen ist und eine hinreichende Bedingung liefert. Somit
> 'müsste' es damit ebenfalls möglich sein.
> Die Frage die bleibt, es müsste auch mit Jaffe's PL
> funktionieren, das ebenfalls eine hinreichende Bedingung
> liefert. Also "muss" es faktisch möglich sein, jedoch hab
> ich das nicht hinbekommen - Nerode ist in diesem Fall auf
> jeden Fall einfach, falls ich keinen Fehler gemacht habe.
> Dennoch - wie gesagt, ein Tipp zu Jaffe wäre interesannt
> :)
Der Weg über Jaffes PL erscheint mir tatsächlich umständlicher zu sein.
Ich beziehe mich auf ![[]](/images/popup.gif) die Wikipedia-Version von Jaffes PL.
Angenommen L wäre regulär. Dann existiert eine Zahl [mm] $n\in\IN$ [/mm] wie in Jaffes PL.
Insbesondere existiert für [mm] $z:=ab^n$ [/mm] eine Zerlegung $z=uvw$ wie in Jaffes PL.
Unterscheide nun die beiden Fälle:
1. $v=a$.
2. [mm] $v\not=a$ [/mm] (somit enthält v mindestens ein $b$).
Im 1. Fall betrachte $i=0$ und [mm] $x=a^{n+1}$ [/mm] und im zweiten Fall $i=2$ und [mm] $x=a^n$, [/mm] um zu einem Widerspruch zu gelangen.
|
|
|
|
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
!
