Matroids Matheplanet Forum Index
Moderiert von Bilbo
Theoretische Informatik » Formale Sprachen & Automaten » Beweis Sprache erfüllt Pumping Lemma
Autor
Universität/Hochschule J Beweis Sprache erfüllt Pumping Lemma
AndrejTheAlien
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.05.2020
Mitteilungen: 11
  Themenstart: 2020-05-13

Ich möchte zeigen, dass die Sprache $L = \{a^m b^n c^n | 1 \le m,n \in \mathbb{N}\} \cup \{b^m c^n | m,n \in \mathbb{N}_0\}$ das Pumping Lemma erfuellt. Bis jetzt habe ich nur geschafft mit dem Beweis unten zu zeigen, dass die erste Menge in der Sprache nicht regulär ist, also das Pumping Lemma nicht erfüllt (Ich hoffe es ist richtig). Also muss die zweite Menge eine Abhilfe schaffen. Aber ich komme leider nicht drauf. Bin dankbar fuer jeden Tipp. LG Andrej Sei $L$ regulaer. Dann gibt es ein $p \ge 1$, so dass jedes $w \in L$ mit $ |w| \ge p$ eine Zerlegung $w = xyz$ hat mit $ |xy| \le p$, $ |y| > 0 $, $ x y^{i}z \in L_{4.2.1}$ fuer alle $i \in \mathbb{N}_{0}$. Wir betrachten $w' = a b^{p}c^{p} \in L$. Es gilt $ |w| \ge p$. Nun muss es fuer $w'$ eine Zerlegung $xyz$ geben. Damit $ |xy| \le p$ erfuellt ist, muss $x=a$, $y = b^{p-k}$ und $z = b^{k} c^{p}$ mit $k > 0$. Zusaetzlich muss $k < p$ sein, damit $ |y| > 0$ ist. Nun bereits fuer $i = 2$ sehen wir, dass $x y^{2} z = a b^{p-k}b^{p-k}b^{k} c^{p} = a b^{p-k}b^{p} c^{p} = a b^{2p-k} c^{p} \not\in L$ da $k < p$.


   Profil
philippw
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.06.2005
Mitteilungen: 1157
Wohnort: Hoyerswerda
  Beitrag No.1, eingetragen 2020-05-14

Hi AndrejTheAlien, und willkommen auf dem Matheplaneten! In deinem Beweis unten ist ein kleiner Fehler: $x=a$ muss nicht gelten, $x$ kann auch von der Form $ab^l$ sein, für $0\leq l\leq p-2$. Der Beweis funktioniert am Ende aber genauso. Der Beweis funktioniert insbesondere auch für die Sprache $L$ selbst, d.h. das Pumping Lemma ist nicht erfüllt. Hast du die Aufgabe vielleicht falsch abgeschrieben? Gruß, Philipp


   Profil
AndrejTheAlien
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.05.2020
Mitteilungen: 11
  Beitrag No.2, vom Themenstarter, eingetragen 2020-05-14

\quoteon(2020-05-14 09:12 - philippw in Beitrag No. 1) In deinem Beweis unten ist ein kleiner Fehler: $x=a$ muss nicht gelten, $x$ kann auch von der Form $ab^l$ sein, für $0\leq l\leq p-2$. Der Beweis funktioniert am Ende aber genauso. \quoteoff Oh ja, stimmt! \quoteon Der Beweis funktioniert insbesondere auch für die Sprache $L$ selbst, d.h. das Pumping Lemma ist nicht erfüllt. Hast du die Aufgabe vielleicht falsch abgeschrieben? \quoteoff Hmm... eig nicht. Die AufgabenStellung lautet: "Zeigen Sie warum die folgende Sprache das Pumping Lemma erfüllt.". Und die Sprache ist auch so wie beschrieben. Aber vllt hat sich der Prof. vertan. Ich frag mal nach. Danke auf jeden Fall Gruss Andrej


   Profil
AndrejTheAlien
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.05.2020
Mitteilungen: 11
  Beitrag No.3, vom Themenstarter, eingetragen 2020-05-15

\quoteon(2020-05-14 09:12 - philippw in Beitrag No. 1) Hi AndrejTheAlien, und willkommen auf dem Matheplaneten! In deinem Beweis unten ist ein kleiner Fehler: $x=a$ muss nicht gelten, $x$ kann auch von der Form $ab^l$ sein, für $0\leq l\leq p-2$. Der Beweis funktioniert am Ende aber genauso. Der Beweis funktioniert insbesondere auch für die Sprache $L$ selbst, d.h. das Pumping Lemma ist nicht erfüllt. Hast du die Aufgabe vielleicht falsch abgeschrieben? Gruß, Philipp \quoteoff Ich habe wohl die Zerlegung $x=\varepsilon$, $y=a$, $z=b^p c^p$ nicht bedacht. Dann ist das Pumping Lemma fuer die erste Menge in $L$ doch erfüllt.


   Profil
philippw
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.06.2005
Mitteilungen: 1157
Wohnort: Hoyerswerda
  Beitrag No.4, eingetragen 2020-05-15

Ah, da hast du Recht. Ich habe den gleichen Fehler gemacht, ich dachte, dass x und y nicht leer sein dürfen, aber nur y muss nicht leer sein. Dann sollte das auch die Antwort für L liefern, oder? Wenn die Frage für dich damit erledigt ist, dann setze doch bitte das Häkchen ("Das Thema ist nun erledigt" beim Antworten). Gruß, Philipp


   Profil
AndrejTheAlien
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.05.2020
Mitteilungen: 11
  Beitrag No.5, vom Themenstarter, eingetragen 2020-05-15

\quoteon(2020-05-15 11:50 - philippw in Beitrag No. 4) Dann sollte das auch die Antwort für L liefern, oder? Wenn die Frage für dich damit erledigt ist, dann setze doch bitte das Häkchen ("Das Thema ist nun erledigt" beim Antworten). \quoteoff Aber was ist mit dem Wort $ab b^p c c^p$? Es ist in der ersten Menge von $L$, ist länger als p und damit $|xy| \le p$ ist, muss $xy=ab$ sein, was sich glaube ich nicht pumpen lässt egal ob $x=\varepsilon$ oder $x \ne \varepsilon$. P.S. Ich denke dran den Hacken zu setzen. Danke fuer die Info


   Profil
philippw
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.06.2005
Mitteilungen: 1157
Wohnort: Hoyerswerda
  Beitrag No.6, eingetragen 2020-05-15

$x=\varepsilon$ und $y=a$ sollte auch hier funktionieren? Damit $|xy|\leq p$ gilt kann $xy$ irgendwas von $a$, $ab$, $abb$, ..., $ab^{p-1}$ sein.


   Profil
AndrejTheAlien
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.05.2020
Mitteilungen: 11
  Beitrag No.7, vom Themenstarter, eingetragen 2020-05-15

\quoteon(2020-05-15 13:27 - philippw in Beitrag No. 6) $x=\varepsilon$ und $y=a$ sollte auch hier funktionieren? Damit $|xy|\leq p$ gilt kann $xy$ irgendwas von $a$, $ab$, $abb$, ..., $ab^{p-1}$ sein. \quoteoff ja stimmt


   Profil
AndrejTheAlien
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.05.2020
Mitteilungen: 11
  Beitrag No.8, vom Themenstarter, eingetragen 2020-05-15

Aber was ist damit: Sei $L$ regulaer. Dann gibt es ein $p \ge 1$, so dass jedes $w \in L$ mit $ |w| \ge p$ eine Zerlegung $w = xyz$ hat mit $ |xy| \le p$, $ |y| > 0 $, $ x y^{i}z \in L_{4.2.1}$ fuer alle $i \in \mathbb{N}_{0}$. Wir betrachten $w' = a b^{p}c^{p} \in L$. Es gilt $ |w| \ge p$. Nun muss es fuer $w'$ eine Zerlegung $xyz$ geben. Damit $ |xy| \le p$ erfuellt ist, kann 1. $x=a$, $y = b^{p-k}$ und $z = b^{k} c^{p}$ mit $k > 0$, 2. oder $x=\varepsilon$, $y=ab^{p-k}$, $z=b^k c^p$, 3. oder $x=\varepsilon$, $y=a$, $z=b^pc^p$ sein. Zusaetzlich muss $k < p$ sein, damit $ |y| > 0$ ist. 1. laesst sich nicht pumpen, denn $x y^{2} z = a b^{p-k}b^{p-k}b^{k} c^{p} = a b^{p-k}b^{p} c^{p} = a b^{2p-k} c^{p} \not\in L$ da $k < p$. 2. laesst sich nicht pumpen, da die Reihenfolge der a und b durcheinander ist. 3. laesst sich nicht pumpen, da $xy^0z = b^p c^p \not\in L$


   Profil
philippw
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.06.2005
Mitteilungen: 1157
Wohnort: Hoyerswerda
  Beitrag No.9, eingetragen 2020-05-15

Zu 3.: $b^pc^p$ liegt in der zweiten Menge von $L$. $m$ und $n$ müssen laut Definition nicht unterschiedlich sein, $m=n=p$ funktioniert.


   Profil
AndrejTheAlien
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 13.05.2020
Mitteilungen: 11
  Beitrag No.10, vom Themenstarter, eingetragen 2020-05-15

\quoteon(2020-05-15 17:24 - philippw in Beitrag No. 9) Zu 3.: $b^pc^p$ liegt in der zweiten Menge von $L$. $m$ und $n$ müssen laut Definition nicht unterschiedlich sein, $m=n=p$ funktioniert. \quoteoff Genau! Dann ist alles gezeigt. Ich danke dir! Ich schliesse dann die Frage.


   Profil
AndrejTheAlien hat die Antworten auf ihre/seine Frage gesehen.
AndrejTheAlien hat selbst das Ok-Häkchen gesetzt.
AndrejTheAlien wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]