You are not logged in.

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

41

Tuesday, February 17th 2004, 8:28pm

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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

42

Tuesday, February 17th 2004, 8:30pm

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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

43

Tuesday, February 17th 2004, 8:39pm

L4:
S->A
A->aB,bB,cB,dB
B->a,b,c,d,aA,bA,cA,dA

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

44

Tuesday, February 17th 2004, 8:44pm

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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

45

Tuesday, February 17th 2004, 8:49pm

oops, stimmt ja.
so finde ich es irgendwieübersichtlicher, frag nicht wieso :rolleyes:

Ray-D

Alter Hase

  • "Ray-D" is male

Posts: 690

Date of registration: Oct 9th 2002

Location: Zimbabwe-Island Ost Beiträge: 3.427

Occupation: Informatiker

46

Tuesday, February 17th 2004, 11:18pm

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. :)
"ob ich alles weiss, was wir wissen, weiss ich auch nicht, aber ich weiss natürlich niemand von uns weiss etwas was er nicht weiss" - Wolgang Schäuble
Freiheit wird nicht erbettelt, sondern erkämpft


Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von »Ray-D« (Heute, 04:29)

This post has been edited 1 times, last edit by "Ray-D" (Feb 17th 2004, 11:19pm)


Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

47

Tuesday, February 17th 2004, 11:34pm

danke danke

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

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

48

Tuesday, February 17th 2004, 11:53pm

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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 7 times, last edit by "Joachim" (Feb 18th 2004, 12:17am)


Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

49

Wednesday, February 18th 2004, 4:14pm

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?

This post has been edited 1 times, last edit by "Uprooter" (Feb 18th 2004, 4:15pm)


  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

50

Wednesday, February 18th 2004, 4:45pm

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?
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

51

Wednesday, February 18th 2004, 4:57pm

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}

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

52

Wednesday, February 18th 2004, 5:03pm

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

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

53

Wednesday, February 18th 2004, 5:27pm

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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 1 times, last edit by "Joachim" (Feb 18th 2004, 5:28pm)


  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

54

Wednesday, February 18th 2004, 5:29pm

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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

55

Wednesday, February 18th 2004, 5:34pm

also heisst das soviel wie pumping lemma voll ausschreiben? wenn ja, dann weiss ich das natürlich, wollte das hier nicht alles reinposten

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

56

Wednesday, February 18th 2004, 5:51pm

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.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

This post has been edited 1 times, last edit by "Joachim" (Feb 18th 2004, 5:52pm)


Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

57

Friday, February 20th 2004, 4:10pm

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. ist das in diesem fall wirklich nötig so ausführlich zu untersuchen oder diente das nur der übun? ich meine, wenn ma einen dieser bereiche verändert, dann können die beiden hälften nicht mehr gleich sein, der interessanteste bereich wäre vielleicht genau zwischen den beiden hälften aber auch nur wenn die 2. hälfte das umgedrehte der ersten wäre. ich meine, wenn man in diesem abschnitt was ändert, dann bleibt höchstens die länge der beiden hälften gleich, die hälften sind dann trotzdem unterschiedlich,da links nur b's stehen und rechts a's...kann man verstehen was ich meine? :rolleyes: 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:12pm)


  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

58

Friday, February 20th 2004, 4:34pm

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ß.
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

59

Friday, February 20th 2004, 4:41pm

ja, ich verallgemeinere es auch nicht auf alle ww-sprachen, aber bei dem wort a^nb^na^nb^n sieht man doch, dass da nix geschehen kann...ich ändere einen teil und dann sind die nicht mehr gleich..vllt bin ich auch zu vorschnell mit dieser einstellung :D

Uprooter

Junior Schreiberling

  • "Uprooter" is male
  • "Uprooter" started this thread

Posts: 249

Date of registration: Oct 7th 2003

Occupation: Angw. Inf.

60

Friday, February 20th 2004, 4:48pm

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.
L7 aus L_2:
S->eps,A
A->aa,aAa
Daraus folgt: L7 aus L_1 und aus L_0

würde das reichen? das lemma natürlich "etwas"ausführlicher...


übrigens: du hast geschrieben, gramm für jeweils kleinste sprache angeben, meintest du vllt die größte?

This post has been edited 1 times, last edit by "Uprooter" (Feb 20th 2004, 4:50pm)