Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Kann gut sein, das Beispiel hab ich mir ausgedacht.Quoted
Original von Uprooter
der beweis, dass L4 nicht regulär ist steht im skript oder irr ich mich?
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Ja, kann man auch auf diese Weise machen. Aber mit a^n b^n ist es natürlich etwas weniger Schreibarbeit.Quoted
Original von Uprooter
eine frage wie man nachweisen kann, dass die sprache L={a^i b^j a^j b^i; i,j >=0} nicht regulär ist:
in der übung wurde x=a^n b^n genommen und mit dem pumping lemma bewiesen, dass L nicht regulär ist....würde es auch mit a^n b^n a^n b^n gehen oder ist es dann genau das gleiche nur doppelt so lang das x?:
auch bei meinem x kann v nur aus a's bestehen und zwar aus den a's am anfang vom wort, wenn ich also die 3 bedingung betrachte und uv^2w wähle, dann gehört das wort offenbar nicht mehr zur sprache, da es am anfang mehr a's gibt als b's am ende des wortes? ist der beweis damit erbracht?
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Das ist aber L5.Quoted
Original von Uprooter
L4:
S->A
A->aB,bB,cB,dB
B->a,b,c,d,aA,bA,cA,dA
Alter Hase
Date of registration: Oct 9th 2002
Location: Zimbabwe-Island Ost Beiträge: 3.427
Occupation: Informatiker
Quoted
Original von Uprooter
eine frage wie man nachweisen kann, dass die sprache L={a^i b^j a^j b^i; i,j >=0} nicht regulär ist:
in der übung wurde x=a^n b^n genommen und mit dem pumping lemma bewiesen, dass L nicht regulär ist....würde es auch mit a^n b^n a^n b^n gehen oder ist es dann genau das gleiche nur doppelt so lang das x?:
auch bei meinem x kann v nur aus a's bestehen und zwar aus den a's am anfang vom wort, wenn ich also die 3 bedingung betrachte und uv^2w wähle, dann gehört das wort offenbar nicht mehr zur sprache, da es am anfang mehr a's gibt als b's am ende des wortes? ist der beweis damit erbracht?
This post has been edited 1 times, last edit by "Ray-D" (Feb 17th 2004, 11:19pm)
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Hmm, da muß ich mir was aus den Fingern saugen. Mal schauen ...Quoted
Original von Uprooter
habt ihr noch n paar gramm's zu den restlichen typen auf lager?
This post has been edited 7 times, last edit by "Joachim" (Feb 18th 2004, 12:17am)
This post has been edited 1 times, last edit by "Uprooter" (Feb 18th 2004, 4:15pm)
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Auch bei NEAs werden die Zustände wie gewohnt bezeichnet. Meinst Du die Zustandsübergangsfunktion? Oder die Umwandlung eines NEA in einen DEA mittels Potenzmengenkonstruktion?Quoted
Original von Uprooter
ne kleine frage zu NEA's:
wieso wird nicht wie bei den DEA's jeder zustand mit z1,z2....oder sonst was bezeichnet, sondern {z1,z2....}? was hat das für einen sinn? ist das notwendig oder nur zum besseren verständniss?
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Das stimmt schonmal nicht. Der NEA auf Seite 8 im Skript hat z. B. "ganz normale" Zustandsnamen.Quoted
Original von Uprooter
ka, weiss nicht was eine potenzmengenkonstruktion ist, aber alle zustände von NEa's, die in den übungen und vorlesungen betrachtet wurden, wurde diese bezeichnung für die zustände benutzt: zB {z1,z2,z3}
This post has been edited 1 times, last edit by "Joachim" (Feb 18th 2004, 5:28pm)
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Richtig. Dazu noch eine Anmerkung: In der Klausur erwarten wir einen formal korrekten Beweis. Deine obige Begründung würde in der Klausur also nur sehr wenige Punkte bringen.Quoted
Original von Uprooter
also L6 ist schon mal nicht regulär, weil ein endlicher automat nicht wissen kann wieviele n's er schon gelesen hat.
mit pumping lemma lässt sich das auch nachweisen und zwar wenn man das wort m^nmmmn^n wählt, dann besteht v nur aus m's und uv^2w gehört nicht zu L6
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Mehr als das. Es heißt:Quoted
Original von Uprooter
also heisst das soviel wie pumping lemma voll ausschreiben?
Dachte ich mir. Wollte es zur Sicherheit nur nochmal erwähnen.Quoted
wenn ja, dann weiss ich das natürlich, wollte das hier nicht alles reinposten
This post has been edited 1 times, last edit by "Joachim" (Feb 18th 2004, 5:52pm)
This post has been edited 1 times, last edit by "Uprooter" (Feb 20th 2004, 4:12pm)
Guru
Date of registration: Dec 11th 2001
Location: Hämelerwald
Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)
Zwischen formalem Beweis und "sehen" gibt es leider einen nicht unwesentlichen Unterschied ...Quoted
Original von Uprooter
eine frage zu beweis, dass die sprache L={ww|w aus {a b}^+} nicht kontextfrei ist(übung 6):
joachim du hast in der übung speziell das wort a^nb^na^nb^n btrachtet und es in 7 bereiche unterteilt, wo vwx reinpassen könnte, so dass |vwx|<=n ist und dann für jeden diese bereiche geguckt, ob beim "aufpumpen" das wort immer noch zu sprache gehört.
[...]
an dem speziellen wort erkennt man doch gleich, dass es zu der sprache nicht gehören kann oder muss es so ausführlich gemacht werden, egal ob mans sieht oder nicht?
This post has been edited 1 times, last edit by "Uprooter" (Feb 20th 2004, 4:50pm)