[FoSAP] Frage zur Musterlösung Ü5 A7 Pumping Lemma

[FoSAP] Formale Systeme, Automaten, Prozesse
[BuK] Berechenbarkeit und Komplexität
[MaLo] Mathematische Logik

Frage zur Musterlösung Ü5 A7 Pumping Lemma

Beitragvon sChUhBiDu » 23.05.11 20:28

Hallo,

und zwar geht es mir um die Musterlösung zum Aufgabenteil b.Hier wurde zur Sprache L_2 = \{uv(vu)^n..., |u| = |v| das passende Wort w = a^n b^n b^n a^n = a^n b^{2n} a^n gewählt.

Wie passt das "passende Wort" in die Sprache? Wählt man für u=a und für v=b passt das doch überhaupt nicht, oder bin ich gerade blind? Da käme ja ab\hspace{2.0cm}babababababa... raus.
sChUhBiDu
 
Beiträge: 22
Registriert: 23.05.11 20:18
Studiengang: ?

Re: Frage zur Musterlösung Ü5 A7 Pumping Lemma

Beitragvon flawless » 23.05.11 21:12

... |u| = |v|


u und v sind Wörter über sigma*
Benutzeravatar
flawless
 
Beiträge: 32
Registriert: 16.10.10 17:13
Studiengang: Informatik (B.Sc.)

Re: Frage zur Musterlösung Ü5 A7 Pumping Lemma

Beitragvon sChUhBiDu » 23.05.11 21:59

Ich verstehe das Kommentar nicht...."a" und "b" sind aus Sigma. Frage durchgelesen?
sChUhBiDu
 
Beiträge: 22
Registriert: 23.05.11 20:18
Studiengang: ?

Re: Frage zur Musterlösung Ü5 A7 Pumping Lemma

Beitragvon m.singh » 23.05.11 22:23

Du darfst das n aus dem Pumping Lemma nicht mit dem n aus der Sprachdefinition verwechseln. In diesem Fall ist das n aus der Sprachdefintion n= 1 und weil |v|=|u| kommt dieser Term zustande...
m.singh
 
Beiträge: 8
Registriert: 05.04.11 18:28
Studiengang: Informatik (B.Sc.)

Re: Frage zur Musterlösung Ü5 A7 Pumping Lemma

Beitragvon sChUhBiDu » 23.05.11 22:41

Ja nice, also ist die Sprache mit n=1 so zu "lesen" uvvu, mit u = a_1...a_n=a^n und v=b_1...b_n=b^n, somit a^n b^n b^n a^n.

Wurde auch in der Globalübung nie deutlich erklärt und es hatten sich einige deswegen gewundert.

Vielen Dank :prost:
sChUhBiDu
 
Beiträge: 22
Registriert: 23.05.11 20:18
Studiengang: ?

Re: Frage zur Musterlösung Ü5 A7 Pumping Lemma

Beitragvon empiraV » 23.05.11 23:01

naja muss hinzufügen das es schon gesagt wurde, da genau die Frage dort kam und aus den einen n's daher ein x gemacht wurde ;) aber hätte es sonst auch nicht verstanden ;)
empiraV
 
Beiträge: 14
Registriert: 03.11.08 16:35
Studiengang: Informatik (B.Sc.)

Re: Frage zur Musterlösung Ü5 A7 Pumping Lemma

Beitragvon C-Otto » 24.05.11 00:20

Danke, empiraV :)
Dr. rer. nat. Carsten Otto
http://verify.rwth-aachen.de/otto/
Benutzeravatar
C-Otto
 
Beiträge: 568
Registriert: 10.08.06 00:20
Wohnort: Schwalbach am Taunus
Studiert seit: fertig
Anwendungsfach: BWL


Zurück zu Theoretische Informatik