Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck turingmaschine pumpinglemma tipp zahlendarstellung cmos bonusklausur klausurrelevant komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop huffman-kodierung cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit hauptklausur vorlesungsfolien polynomialzeitreduktion kontextfreie-sprache faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten mealy lambda endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort moore ohne-lösungen betriebssystem speicherorganisation monotone-grammatik 2-komplement hammingzahl lösungsweg fehler pumping-lemma-für-kontextfreie-sprachen pumping-lemma reguläre-sprache monoton kodierung berechenbarkeit klausureinsicht disjunktive-normalform abzählbarkeit info-ii bussysteme rechnerarchitektur entscheidbarkeit komplexitätsklassen chomsky-klassen ableitungsbaum vorlesungsaufzeichnung round-robin aufzählbarkeit minimierung-endlicher-automaten von-neumann-rechner binärzahl entscheidbar programmiersprachen stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 1 Minuspunkt
38 Aufrufe

Hallo,

habe eine allgemeinere Frage zum Punmping Lemma. Da das doch ein Widerspruchsbeweis ist, müsste es doch eigentlich auch klappen, dass man nur ein Gegenbeispiel anführt.

Also am Beispiel von Aufgabe a):

1. Annahme: Es existiere eine EA mit n Zuständen, der L3 akzeptiert.

Das Wort w = aaaa ist Element von L3 (i=2).

2. Aufteilung von w. w=xyz mit
x = Lamda (leeres Wort)
y = a
z = aaa

3. Dann müsste \( xy^{2}z \) auch Element von L3 sein, aber
\( xy^{2}z = aaaaa \), also nicht Element von L3, da sich kein i finden lässt, dass dieses Wort erzeugt.

-> Widerspruch, L3 ist nicht regulär.

Geht das?

Grüße, Julian

 

in HU-1-4 von uafjv uafjv Tutor(in) (168k Punkte)  

2 Antworten

0 Pluspunkte 0 Minuspunkte

Hallo Julian,

ganz so einfach geht das leider nicht. In deinem Fall hast du gezeigt, dass das ganze für i=2 nicht gilt, also für einen Spezialfall. Du müsstest das theoretisch für alle n aus den natürlichen Zahlen machen, um das ganze komplett zu beweisen. 

Es muss beim Pumping-Lemma also immer gezeigt werden, dass es für ein variables n gilt.

Ich hoffe, ich konnte dir helfen.

Max (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 Pluspunkte 0 Minuspunkte

Nein, das geht aus 2 Gründen nicht:

1. Für dein Wort ("aaaa") gilt die Bedingung \( |w| \leq n \) nur für \( n \leq 4 \). Wie bereits oben vom den Übungsleitern und mir erklärt, kann das n/die Anzahl Zustände des EA aber beliebig groß sein und darf im Beweis nicht auf einen festen Wert gesetzt werden.

2. Das Pumpinglemma sagt nur aus, dass (mindestens) eine Aufteilung xyz existiert, bei der man das y pumpen kann. Das heißt nicht, dass man bei jeder Aufteilung das y pumpen kann und das entstandene Wort noch in der Sprache ist. Du musst also für den Widerspruch zeigen, dass keine solche Aufteilung existiert. Eine einzelne Aufteilung heraus zu greifen, reicht nicht aus, da es eine  andere Aufteilung geben kann, mit der das Pumpinglemma erfüllt ist.

Grüße,

Tobias (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
...