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 pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur 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 cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

1 Pluspunkt 1 Minuspunkt
33 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)  
...