Fachrat Informatik - Forum

Quoted

Original von Uprooter
der beweis, dass L4 nicht regulär ist steht im skript oder irr ich mich?

Kann gut sein, das Beispiel hab ich mir ausgedacht.

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?

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
L4:
S->A
A->aB,bB,cB,dB
B->a,b,c,d,aA,bA,cA,dA

Das ist aber L5.

Ist korrekt so. Man könnte jedoch A noch durch S ersetzen und die erste Produktion streichen.

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?

das wort a^n b^n a^n b^n gehört auch zur sprache L (i=j=n). die änge des wortes ist dann aber 4n, nicht wie in der übung 2n. uv schliesst nur die ersten a´s ein und beim pumpen erhalten wir a^m b^n a^n b^n, m != n und somit ist der beweis auch erbracht.

Quoted

Original von Uprooter
habt ihr noch n paar gramm's zu den restlichen typen auf lager?

Hmm, da muß ich mir was aus den Fingern saugen. Mal schauen ...

L_6 := {w aus {m, n}^* | |w|_m = |w|_n + 3}
L_7 := {ww | w aus {a}^*}
L_8 := {a^n b^n c^n d^n | n aus N_0}
L_9 := {0^(n^2) | n aus N_0} (Achtung, schwer!)
L_10 := {a^n b^n c^m d^m e^n f^n | m, n aus N_0}
L_12 := {w w w^R | w aus {a, b}^*} (auch etwas schwieriger)


Für diese Sprachen bitte angeben (und begründen), zu welchen Sprachklassen sie gehören, und eine Grammatik für die jeweils kleinste Sprachklasse erstellen. Für die Sprachen, die nicht regulär sind, kann man ja mal einen Beweis dieser Eigenschaft per Pumping Lemma versuchen (Pumping Lemma ist mit an Sicherheit grenzender Wahrscheinlichkeit Klausurthema) – ich kann aber nicht garantieren, daß das einfach ist.


Und als Bonus:

L_11 := {0^f | f ist eine Fibonacci-Zahl}

Man zeige mit dem Pumping-Lemma für kontextfreie Sprachen, daß diese Sprache nicht kontextfrei ist. (Auch ziemlich schwer, aber wer das hinbekommt, braucht sich wegen des Pumping Lemmas keine Sorgen mehr zu machen.)

Hinweis: Die ganzen Formeln bei dem angegebenen Link benötigt man nicht. Es reicht völlig aus zu wissen, daß der Abstand zwischen zwei aufeinander folgenden Fibonacci-Zahlen von Zahl zu Zahl größer wird.

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?

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
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}

Das stimmt schonmal nicht. Der NEA auf Seite 8 im Skript hat z. B. "ganz normale" Zustandsnamen.

Mit Potenzmengenkonstruktion ist die Umwandlung eines NEA in einen DEA nach dem in der Vorlesung und Übung behandelten Verfahren gemeint.

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

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 heisst das soviel wie pumping lemma voll ausschreiben?

Mehr als das. Es heißt:

• Pumping Lemma hinschreiben
  
• Annahme des indirekten Beweises hinschreiben
  
• gewähltes Wort x hinschreiben
  
• Hinschreiben und erklären, was u, v und w bei diesem Wort x genau sind.
  
• Hinschreiben und erläutern, warum das Pumping Lemma hier nicht gelten kann
  
• daraus folgern, daß die Sprache nicht regulär ist
  

Quoted

wenn ja, dann weiss ich das natürlich, wollte das hier nicht alles reinposten

Dachte ich mir. Wollte es zur Sicherheit nur nochmal erwähnen.

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?

Zwischen formalem Beweis und "sehen" gibt es leider einen nicht unwesentlichen Unterschied ...

Und gerade bei Sprachen wie {ww | ...} finde ich es nicht unbedingt einfach, mit Sicherheit zu sagen, daß etwas sofort klar ist. Ich dachte während der Vorbereitung auf die Übung zuerst auch, man könnte den Beweis einfacher führen, aber es gibt ein paar unschöne Fälle, die einem da Probleme bereiten können.

Aber keine Sorge, in der Klausur gibt es bestimmt keine Sprache zu untersuchen, bei der man so viele Fälle unterscheiden muß.