Theoretische und technische Informatik - ganz praktisch - Letzte Fragen in PUM-AA

Pumping Lemma 2018-H-03

Sun, 07 Mar 2021 13:40:55 +0000

Hallo,

man kann doch als Pumpwort auch aⁿbⁿc²ⁿdⁿeⁿ nehmen oder?

ich hätte dann so weitergemacht:

xy = a^k 1<= k <= n
y = a^j
x = a^k-j
z = a^n-kbⁿc²ⁿdⁿeⁿ

und dann kann man mit i=0 doch auch zeigen dass das Wort nicht mehr in L liegt oder?

Beste Grüße

Kommt PPL für Kontextfreie Grammatik dran oder nicht?

Sat, 08 Feb 2020 10:09:48 +0000

Wurde in der Zusammenfassung einmal durchgestrichen und einmal nicht

Pumping-Lemma Wortwahl

Wed, 29 Jan 2020 20:17:25 +0000

Hallo,

mal eine Frage zur Wortwahl beim Pumping-Lemma:

Bei der Aufgabe im Buch ist es ja so, dass für alle Wörte der Sprache einfach nur Anzahl Einsen in w = Anzahl Nullen in w sein muss. Nun wird aber als zu testendes Wort 0^n1^n gewählt. Das deckt ja aber jetzt nicht die komplette Sprache ab, sondern nur Wörter der Form 01,0011,000111, etc. . Allerdings werden durch das Wort Wörter wie 0101, 1001, etc. also alle Wörter in denen zwar die Anzahl der Einser = der Anzahl der Nullen ist, aber nicht unbedingt alle Nullen und Einsen hintereinander stehen, ja nicht abgedeckt, obwohl diese noch Bestandteil der Sprache wären, Deswegen die Frage: Muss man bei der Wortwahl ein Wort wählen, dass die komplette Sprache abdeckt, oder reicht ein Wort das zumindest einen Teilbereich der Sprache abdeckt? Dass es nicht reicht ein spezifisches Wort zu testen wurde ja schon beantwortet.

Danke schon mal!

Pumping Lemma Beweisführung welche Sprachen ?

Sat, 04 Jan 2020 23:06:31 +0000

In den Übungsaufgaben aus dem Buch zur theoretischen Informatik werden Pumping Lemma Beweisaufgaben abweichend zur regulären Sprachen gestellt.Für welche Sprachen müssen wir den Beweis erbringen können, da in der Vorlesung und im Tutorium nur die reguläre Sprachen im Zusammenhang mit dem Pumping Lemma behandelt wurde?

Zusammenhang der kontextfreiensprache in Grammatik in Bezug zum PPL

Thu, 07 Feb 2019 15:05:59 +0000

Hallo an Alle,

Ich frage mich, wieso bei den kontextfreien Sprachen immer gegeben sein soll, dass es zwei Pumpstellen bei hinreichend großen Wörtern gibt. Grundsätzlich habe ich das Konzept, dass bei längeren Wörtern als Anzahl an Zuständen vorhanden ist, es Schleifen in der Grammatik geben muss, verstanden. Nun wird aber (allen voran bei dem PPL der kontextfreien Sprachen) immer wieder erklärt, dass es (1) zwei Pumpstellen gibt, die (2) immer gleich groß sein sollen. Hier sind auch noch SC der Überlegung im Text und die dazugehörige Skizze, die das Ganze erläutert:

Nun verstehe ich nicht ganz, wieso es immer zwei Pumpstellen geben muss, bzw wieso die dann auch noch gleich groß sein sollen?
Im Kopf habe ich dabei immer eine kontextfreie Sprache, die ja auch in CNF dargestellt werden kann.
Nun habe ich mir eine Grammatik überlegt, die Wörter produziert, deren Länge die Anzahl der Zustände übertrifft:

Dabei habe ich in B eine Produktion von sich selbst, was mir die Schleifen eines PPL ermöglicht. Nun kann ich mein Wort ja wie unten beschrieben ableiten, ohne , dass neben dem grün markierten B links und rechts die gleiche Menge gepumpt wird. Da jede kontextfreie Sprache in CNF dargestellt werden kann, weiß ich also nicht, woher diese immer zwei gleich großen Pumpstellen genau herkommen sollen.

Ich würde mich sehr über jede Antwort freuen,

Grüße!

Antwort Formulierung

Sun, 12 Feb 2017 09:07:50 +0000

Hallo,

bei PPL Aufgaben reicht es die Kontraposition des PPL zu schreiben um zu zeigen, dass die Sprache nicht regulär/kontextfrei ist oder muss man auch die Annahme mit den 3 Bedingungen am Anfang schreiben ?

Danke

Reicht ein speziefisches Wort zur Widerlegung des Pumpinglemmas?

Thu, 26 Jan 2017 08:15:28 +0000

Hallo,

reicht es nicht nur ein ganz speziefisches Wort einer Sprache zu suchen und dort genau x,y und z zu benennen ohne irgendwelche Hochzahlen?

Es handelt sich beim Pumpimglemma ja um einen Widerspruchsbeweis bei dem es eigentlich ja genügen sollte nur eine Möglichkeit zu finden es zu widerlegen. Wenn es ein Wort gibt für das das Pumpinglemma nicht gilt dann kann es ja auch nichtmehr für alle Wörter gelten.

Ausreichender Beweis

Sat, 14 Jan 2017 15:06:46 +0000

Ist folgender Beweis für die (Bonus-)Klausur ausreichend oder fehlt hier noch etwas?

Pumping-Lemma

Thu, 11 Feb 2016 09:07:11 +0000

Wie ausführlich muss eine Lösung beim Pumping-Lemma sein? Reicht es das Pumping-Lemma formal aufzuschreiben und das Wort anzugeben, dass betrachtet wird. Wie man das Wort zerlegt, aber nur umgangssprachlich? Die Musterlösungen unterscheiden sich da.

Definitionsbereiche von n bei PPL

Tue, 09 Feb 2016 17:24:38 +0000

Was sind die Definitonsbereiche von n für

-das PPL für reguläre Sprachen

-das PPL für kontextfreie Sprachen?

Der einführende Satz lautet ja:

"Es existiert eine Konstante n element N / N_0, sodass für alle w element L mit w größer gleich n ...."

Wann nehme ich N, wann N_0 ?

PPL zum Nachweis regulärer Sprachen geeignet?

Tue, 25 Nov 2014 09:54:20 +0000

Hallo,

noch mal zwei kurze Fragen zum generellen Verständnis des PPL:

1) Wenn man in dieser Aufagbe für jede beliebige Pumpvaribale (aus N inkl. 0) am Ende immer auf das Wort $w=0^n1^n$ kommen würde, dann wäre das PPL erfüllt? Oder auf was muss man am Ende kommen, damit PPL erfüllt ist?

2) Angenommen das PPL wäre erfüllt, dann heißt das aber noch nicht, dass die Sprache wirklich vom EA erkannt wird bzw. dass ein EA zur Sprache existiert?

Danke und Gruß

alternative Argumentation: richtig?

Tue, 25 Nov 2014 09:39:31 +0000

Ich habe auch wie in der Lösung $w=0^n 1^n$ gesetzt. Kann ich dann wie folgt weiter beweisen?

$xy=0^n$ (somit ist der Betrag(xy)=n also PPL-Voraussetzung erfüllt)

$y=0^1=0$

$x=0^{n-1}$

$z=1^n$

mit (3) aus dem PPL folgt:

$w=xy^iz=0^{(n-1)^*} 0^{i^*} 1^n$

offensichtlich folgt mit i>1 das L nicht Teil eines EA ist.

Ist Widerspruchsbeweis durch definieren von xy & z zulässig?

Tue, 25 Nov 2014 09:20:06 +0000

"...müssen wir für alle Zerlegungen zeigen, dass sie 1-3 nicht erfüllen können..."

Heißt das, man kann xy nicht definieren als $1^n$ und z als $0^n$ und dann unter der Bedingung $x=1^j$ und $y=1^{n-j}$ das y aufpumpen mit beliebigen i um zu zeigen, dass unterschiedliche Anzahl von einsen und nullen herauskommt?

Mit anderen Worten, darf ich die einsen als xy definieren und die nullen als z oder zeige ich den Wiederspruch damit nicht allgemeingültig?

PPL für jede Zerlegung ?

Tue, 25 Nov 2014 09:11:55 +0000

EDIT: Der folgende Beitrag bezieht sich auf eine veraltete Version des Pools; er wird trotzdem nicht zensiert, damit die Diskussion in diesem Thread verständlich bleibt.

Hallo,

die Beweisstruktur in diesem Beweis ist nicht korrekt! Es wird etwas falsches gefolgert:

"...Jetzt sei w=xyz beliebige Partition von w. Dann gilt laut PPL:

1) |xy|≤n

2) |y|>0

3)...

Diese Folgerung ist doch falsch. Das PPL sagt nämlich, dass es eine Partition gibt, sodass 1-3 gilt. Also insbesondere, dass es nicht für eine beliebige Partition gilt! Sonst müsste es im PPL heißen, dass dies für jede(!) Zerlegung gilt.

lg Adam