Fachrat Informatik - Forum
FACHSPEZIFISCHE DISKUSSIONEN
Grundlagen der Informatik
klausurvorbereitungen theoinf
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Friday, February 20th 2004, 4:56pm
Wieso nicht? Wenn z. B. v = aa gilt, dann ist uv^2w = a^{2n+2} = a^{n+1}a^{n+1} wieder Wort aus der Sprache.
Quoted
Original von Uprooter
zu L7:
die sprache ist nicht regulär, denn wenn man das lemma auf das wort x=a^na^n anwendet, dann kann v nur aus den ersten a's bestehen und für zB i=2 ist x nicht aus L7.
Nö. Ich meinte das genau so wie ich das geschrieben habe. Die Klasse der regulären Sprachen ist z. B. eine echte Teilmenge der Klasse der kontextfreien Sprachen. Daher ist die Klasse der regulären Sprachen kleiner als die Klasse der kontextfreien Sprachen.
übrigens: du hast geschrieben, gramm für jeweils kleinste sprache angeben, meintest du vllt die größte?
Friday, February 20th 2004, 4:58pm
This post has been edited 1 times, last edit by "Uprooter" (Feb 20th 2004, 5:14pm)
Monday, February 23rd 2004, 11:53am
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, February 23rd 2004, 12:54pm
Grammatiken sind eine Möglichkeit, eine Sprache zu definieren, also festzulegen, welche Wörter zur Sprache gehören und welche nicht.
Original von larzan
wie funktioniert das mit den produktiuonen bei den grammatiken?!
kann ich die S produktion sooft anwenden wie ich lustig bin (also k-mal) und wende dann jede andere produktion in der gegebenen reihenfolge sooft an bis sie nichts mehr verändert, oder wie soll das gehen.
This post has been edited 1 times, last edit by "Joachim" (Feb 23rd 2004, 12:56pm)
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Monday, February 23rd 2004, 9:26pm
Ich verstehe leider nicht, was Du meinst.
Original von larzan
dann geht es also darum darauf zu achten das man keine produktionen hat die eine zeichenfolge erstellen die man nicht mit irgendeiner andern produktion/en so umwandeln kann, das am ende theoretisch bei beliebig vielen verwendeten prod. der endzustand erreicht ist.!?
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Tuesday, February 24th 2004, 1:47pm
Sei L eine Sprache über dem Alphabet Sigma (also ist L eine Teilmenge von Sigma^*).
Original von Uprooter
was ist das Komplement einer sprache oder zu einer sprache?
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Tuesday, February 24th 2004, 4:29pm
Falls Du mit L die Sprache über {0, 1} meinst, die nur gerade Wörter enthält, die jeweils "00" oder "11" enthalten, dann kann man das nicht so machen. L ist dann nämlich regulär.
Original von NullAhnung
1)Pumpimg Lemma
Wenn L= w € (0,1)* | w_1 00 w_2 oder w_1 11 w_2 und |w| gerade
x= 0^n001^n = 0^(n+2)1^n
u=0^k v = 0^l k+l-2 <= n
w=0^(n-k-l+2)1^n
uv^2w = 0^(n+l+2) 1^n <> L
Kann man das so machen? Nur noch mit n paar Erklärungen dazu denk ich.
Der Unterstrich ist einfach die Kennzeichnung für ein neues Symbol. A und A sind verschiedene Symbole.
3) Was bedeutet der Unterstrich bei dem Kellerautomat in Übung 5? Heißt das nur, dass da der Anfang ist?
Das weiß ich leider nicht, da ich nicht die Klausuraufgaben stelle. Ich halte dies aber durchaus für möglich, dann aber für eine einfache Sprache.
4)Kommt das Pumping Lemma für kontextfreie Sprachen auch dran
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Tuesday, February 24th 2004, 4:40pm
Bis hierhin hast Du recht.
Original von Uprooter
aalso, L8 ist nicht regulär weil: wende ich das lemma auf a^nb^nc^nd^n an, dann besteht v nur aus a's und wenn ich den teil dann aufpumpe gehört das wort nicht mehr zur sprache.
die sprache ist auch nicht kontextfrei denn:
wende ich das lemma für typ2-sprachen auf das gleiche wort an, dann lässt sich das wort in 7 bereiche unterteilen, also kann vwx nur im bereich der a's, b's, c's oder d's oder auch jeweils dazwischen liegen. wenn man dann eins davon aufpumpt stimmt die anzahl der restlichen buchstaben mit dem in diesem bereich nciht mehr überein, also gehört das wort nicht zur sprache.
Das stimmt auch noch.
die sprache ist aber kontextsensitiv:
Das aber nicht. Mit dieser Grammatik erzeugst Du alle Wörter, die die gleiche Anzahl von "a"s, "b"s, "c"s und "d"s haben. Gefragt war aber nach a^n b^n c^n d^n.
G={{S,A}, {a,b,c,d}, P, S}
S->eps,A
A->abcd, abcdA
dann alle möglichen kombinationen aus 2 buchstaben zB
ab->ba, ba->ab, ca->ac, ac->ca....etc
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Tuesday, February 24th 2004, 5:15pm
Damit läßt sich beispielsweise das Wort "aaaaaaaaaaabcd" erzeugen.
Original von Uprooter
duh, hab mich irgendwie gehen lassen, so vllt?:
S->eps,abcd
a->aa
b->bb
c->cc
d->dd
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Tuesday, February 24th 2004, 8:17pm
Eigentlich sollte ich bereits oft genug gesagt haben, wie wir uns einen Beweis in der Klausur vorstellen (insbesondere wie Herr Vollmer ihn sich vorstellt). Hier nun eine Musterlösung für L_6. Das war's dann aber auch erstmal mit Fragen der Art "wie soll das aussehen?" ...
Original von larzan
ich habe mal ne frage zu L6, das pumping lemma :
wie genau müsste man denn eine korrekte antwort formulieren?
so ?
|x| = 2n+3 >= n
x kann m und n in beliebiger reihenfolge enthalten, mit (1) |v|>=1
und (2) |u v^i w|=|x| mit i >=0 wird das verhältnis von m zu n verändert und entspricht demzufolge nicht mehr der anforderung |w|_m = |w|_n +3 und ist kein element der sprache
oder wie müsste es lauten?
This post has been edited 3 times, last edit by "Joachim" (Feb 24th 2004, 8:45pm)
Wednesday, February 25th 2004, 9:58am
Original von Joachim
Falls Du mit L die Sprache über {0, 1} meinst, die nur gerade Wörter enthält, die jeweils "00" oder "11" enthalten, dann kann man das nicht so machen. L ist dann nämlich regulär.
Original von NullAhnung
1)Pumpimg Lemma
Wenn L= w € (0,1)* | w_1 00 w_2 oder w_1 11 w_2 und |w| gerade
x= 0^n001^n = 0^(n+2)1^n
u=0^k v = 0^l k+l-2 <= n
w=0^(n-k-l+2)1^n
uv^2w = 0^(n+l+2) 1^n <> L
Kann man das so machen? Nur noch mit n paar Erklärungen dazu denk ich.
Wednesday, February 25th 2004, 11:23am
Original von NullAhnung
Nein ich meine damit die Sprache, die in der Mitte des Wortes 00 oder 11 hat. Das Wort selber soll ne grade Anzahl haben.
Original von NullAhnung
x= 0^n001^n = 0^(n+2)1^n
u=0^k v = 0^l k+l-2 <= n
w=0^(n-k-l+2)1^n
uv^2w = 0^(n+l+2) 1^n <> L
