You are not logged in.

sr409

Junior Schreiberling

Posts: 156

Date of registration: Jan 3rd 2003

61

Tuesday, February 11th 2003, 4:40pm

Großes Danke an Joachim für die Hilfestellungen :)

sr409

Junior Schreiberling

Posts: 156

Date of registration: Jan 3rd 2003

62

Tuesday, February 11th 2003, 4:42pm

Aufgabe: 9.2: Geben Sie eine 2-Band Touringmaschine an, die die Sprache { ww | w Element von {0,1}* } akzeptiert.

Ich denk ne 2-Band Maschine krieg ich hin. Nur mir fällt irgendwie kein guter Algorithmus ein, mit dem ich zeigen kann, dass w zweimal hintereinander vorkommt. Irgendwer n Tip ?

sebi

Junior Schreiberling

  • "sebi" is male

Posts: 153

Date of registration: Dec 10th 2001

Location: Hannover, Erde

Occupation: lebenskünstler

63

Tuesday, February 11th 2003, 4:46pm

ich habs jetzt glaube ich endlich kapiert :) vielen dank an joachim & spike & den rest :)

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

64

Tuesday, February 11th 2003, 4:59pm

Quoted

Original von sr409
Aufgabe: 9.2: Geben Sie eine 2-Band Touringmaschine an, die die Sprache { ww | w Element von {0,1}* } akzeptiert.

Ich denk ne 2-Band Maschine krieg ich hin. Nur mir fällt irgendwie kein guter Algorithmus ein, mit dem ich zeigen kann, dass w zweimal hintereinander vorkommt. Irgendwer n Tip ?
Man könnte folgendermaßen vorgehen:

Zu Beginn steht ein Wort x auf Band 1.
  1. Positioniere den Schreib-/Lesekopf von Band 1 auf die Wortmitte (die Wortmitte läßt sich durch Abzählen mit Hilfe von Band 2 bestimmen, wie das geht kann ich aber bei Interesse nochmal genau erläutern)
  2. Lösche Band 2
  3. Schreibe die zweite Hälfte des Wortes von Band 1 auf Band 2, lösche dabei die gelesenen Zeichen von Band 1
  4. Vergleiche Band 1 und 2 -- haben sie einen identischen Inhalt, wird x akzeptiert
    [/list=1]
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

pj

Praktikant

Posts: 13

Date of registration: Nov 27th 2002

65

Tuesday, February 11th 2003, 5:07pm

Weitere Antwort Aufgabe 9.2:

Wie in den Übungen gezeigt ist das wichtigste, den Lesekopf in die Mitte des Wortes zu bekommen. Klar ist, Wörter mit ungeraden Wortlängen sind nicht in der Sprache.

Ein Algorithmus:
Kopiere das Wort von Band1 nach Band2.
(Danach steht der Lesekopf am Ende von ww auf Band1 sowie Band2.)
Gehe rückwärts auf Band1 mit 2 Schritten während auf Band2 nur ein Schritt gemacht wird (sozusagen mit halber Geschwindigkeit).
(Dann steht man auf Band1 am Wortanfang und auf Band2 in der Wortmitte.)
Vergleiche die beiden Wörter, bis Du auf Band2 ans Ende kommst - fertig.

Die Ausformulierung in der Delta-Funktion ist vielleicht das wichtigere hier, d.h. die Zustandsübergänge...

pj

sr409

Junior Schreiberling

Posts: 156

Date of registration: Jan 3rd 2003

66

Tuesday, February 11th 2003, 5:15pm

Ahh ... Danke :) Genau das war nämlich mein Problem...das Ding in die Mitte des Wortes zu kriegen. Thx.

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

67

Tuesday, February 11th 2003, 6:08pm

@pj... wie genau geht das jetzt per definition, dass die auf Band1 doppelt so schnell wie auf Band2 geht? kannst du mal ein beispiel angeben? danke


edit: + wie positionier ich das nochmal in die mitte des wortes? hab die lösung zu übung9 verschlampt :(
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

68

Tuesday, February 11th 2003, 6:27pm

Quoted

Original von vier
@pj... wie genau geht das jetzt per definition, dass die auf Band1 doppelt so schnell wie auf Band2 geht? kannst du mal ein beispiel angeben? danke


Die TM benutzt datür zwei Zustände: In einem Zustand läuft sie einen Schrittt auf Band 1 und bleibt auf Band 2 stehen und im anderen Zustand läuft sie sowohl auf Band 1 als auch auf Band 2 einen Schritt. Die TM wechselt zwischen den beiden Zuständen hin und her.

Ausschnitt aus der Überführungsfunktion:

z1 x y -> z2 x y R N
z2 x y -> z1 x y R R

Dabei kann x y eine beliebige Kombination von 0 und 1 sein.

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

69

Tuesday, February 11th 2003, 6:52pm

ah danke matthias :) echt du bist der einzige übungsleiter der im forum auch posted... super!

edit:
hab gleich mal die Aufgabe versucht zu lösen
{ww|w € {0,1}*} , %=blank

Band1 auf Band2 kopieren:
z0 0 % -> z0 0 0 R R
z0 1 % -> z0 1 1 R R

Band kopiert:
z0 % % -> z1 % % L L

Bis auf Mitte des Bandes2 gehen:
z1 0 0 -> z2 0 0 L N
z1 1 1 -> z2 1 1 L N
z1 0 1 -> z2 0 1 L N
z1 1 0 -> z2 1 0 L N

z2 0 0 -> z1 0 0 L L
z2 0 1 -> z1 0 1 L L
z2 1 0 -> z1 1 0 L L
z2 1 1 -> z1 1 1 L L

Stop wenn an Anfang von 1 und somit in der Mitte von Band2:
z1 % 0 -> z3 % 0 R R
z1 % 1 -> z3 % 1 R R
z2 % 0 -> z3 % 0 R R
z2 % 1 -> z3 % 1 R R

Abgleichen ob erste Hälfte von Band1 = zweite Hälfte Band2:
z3 0 0 -> z3 0 0 R R
z3 1 1 -> z3 1 1 R R
z3 1 % -> ze 1 % N N
z3 0 % -> ze 0 % N N


geht das so? :) also ich seh kein beispiel wo es nicht geht...
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

pj

Praktikant

Posts: 13

Date of registration: Nov 27th 2002

70

Tuesday, February 11th 2003, 7:01pm

Ja, danke Matthias. Echt supi 8) :) ;)

Wenigstens einer, auf den man sich verlassen kann...

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

71

Tuesday, February 11th 2003, 7:07pm

dann müsste das so korrekt sein für aufgabe9.2, oder?

Voraussetzung: auf Band 1 ist das zu überprüfende Wort und Band 2 ist mit # ausgefüllt.

UPDATED !

z0,1,# -> z0,1,1,R,R
z0,0,# -> z0,0,0,R,R
z0,#,# -> z1,#,#,L,N

z1,#,# -> z4,#,#,NN
z1,0,# -> z2,0,#,L,L
z1,1,# -> z2,1,#,L,L
z1,0,1 -> z2,0,1,L,L
z1,1,0 -> z2,1,0,L,L
z1,0,0 -> z2,0,0,L,L
z1,1,1 -> z2,1,1,L,L
z1,#,1 -> z3,#,1,R,N
z1,#,0 -> z3,#,0,R,N

z2,0,1 -> z1,0,1,L,N
z2,0,0 -> z1,0,0,L,N
z2,1,0 -> z1,1,0,L,N
z2,1,1 -> z1,1,1,L,N

z3,0,0 -> z3,0,0,R,R
z3,1,1 -> z3,1,1,R,R
z3,0,# -> z4,0,#,N,N
z3,0,# -> z4,0,#,N,N

z4 ist Endzustand

Cipher

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

72

Tuesday, February 11th 2003, 7:19pm

Quoted

Original von Cipher
dann müsste das so korrekt sein für aufgabe9.2, oder?

Voraussetzung: auf Band 1 ist das zu überprüfende Wort und Band 2 ist mit # ausgefüllt.

z0,1,# -> z0,1,1,R,R
z0,0,# -> z0,0,0,R,R
z0,#,# -> z0,#,#,L,N

z1,0,# -> z2,0,#,L,L
z1,1,# -> z2,1,#,L,L
z1,0,1 -> z2,0,1,L,L
z1,1,0 -> z2,1,0,L,L
z1,0,0 -> z2,0,0,L,L
z1,1,1 -> z2,1,1,L,L
z1,#,1 -> z3,#,1,L,L
z1,#,0 -> z3,#,0,L,L

z2,0,1 -> z1,0,1,L,N
z2,0,0 -> z1,0,0,L,N
z2,1,0 -> z1,1,0,L,N
z2,1,1 -> z1,1,1,L,N

z3,0,0 -> z3,0,0,R,R
z3,1,1 -> z3,1,1,R,R
z3,0,# -> z4,0,#,N,N
z3,0,# -> z4,0,#,N,N

z4 ist Endzustand

Cipher



Beinahe! Ein paar Flüchtigkeitsfehler:

z0,#,# -> z0,#,#,L,N muss heißen z0,#,# -> z1,#,#,L,N
z1,#,1 -> z3,#,1,L,L muss heißen z1,#,1 -> z3,#,1,R,N
z1,#,0 -> z3,#,0,L,L muss heißen z1,#,0 -> z3,#,0,R,N


Edit: Auweia, jetzt hab ich selbst noch was vergessen. Das leere Wort muss auch akzeptiert werden (warum?). Deshalb fehlt noch der Befehl

z1,#,# -> z4,#,#,N,N

Arne

ThI

  • "Arne" is male

Posts: 1,798

Date of registration: Oct 7th 2002

Location: Hannover :)

Occupation: Lecturer ThI

73

Tuesday, February 11th 2003, 7:22pm

aah kann sich wer auch mal meins anschauen? :) hab das per edit eingefügt... etwas weiter oben.. danke schonma =)
"NP - The class of dashed hopes and idle dreams." Complexity Zoo

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

74

Tuesday, February 11th 2003, 7:34pm

Quoted

Original von vier
ah danke matthias :) echt du bist der einzige übungsleiter der im forum auch posted... super!

edit:
hab gleich mal die Aufgabe versucht zu lösen
{ww|w € {0,1}*} , %=blank

Band1 auf Band2 kopieren:
z0 0 % -> z0 0 0 R R
z0 1 % -> z0 1 1 R R

Band kopiert:
z0 % % -> z1 % % L L

Bis auf Mitte des Bandes2 gehen:
z1 0 0 -> z2 0 0 L N
z1 1 1 -> z2 1 1 L N
z1 0 1 -> z2 0 1 L N
z1 1 0 -> z2 1 0 L N

z2 0 0 -> z1 0 0 L L
z2 0 1 -> z1 0 1 L L
z2 1 0 -> z1 1 0 L L
z2 1 1 -> z1 1 1 L L

Stop wenn an Anfang von 1 und somit in der Mitte von Band2:
z1 % 0 -> z3 % 0 R R
z1 % 1 -> z3 % 1 R R
z2 % 0 -> z3 % 0 R R
z2 % 1 -> z3 % 1 R R

Abgleichen ob erste Hälfte von Band1 = zweite Hälfte Band2:
z3 0 0 -> z3 0 0 R R
z3 1 1 -> z3 1 1 R R
z3 1 % -> ze 1 % N N
z3 0 % -> ze 0 % N N


geht das so? :) also ich seh kein beispiel wo es nicht geht...


Auch wieder beinahe richtig! Aber deine TM akzeptiert auch Wörter der Form waw und wbw (also z.b aabaa). Du musst beim Laufen nach links aufpassen, das die Eingabe gerader Länge ist. Wenn das nicht der Fall ist, darf die TM nicht akzeptieren. Wenn du die Befehle

z2 % 0 -> z3 % 0 R R
z2 % 1 -> z3 % 1 R R

löschst, dann stimmt die TM plötzlich, denn in die Situation z2 % x kann sie nur kommen, wenn die Eingabe ungerade Länge hat. Probier's aus!

Ach ja: Es fehlt auch wieder der Befehl

z1 % % -> ze % % N N

zum Akzeptieren des leeren Wortes.

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

75

Tuesday, February 11th 2003, 7:37pm

Quoted

Original von Spike

Quoted

Original von Cipher
dann müsste das so korrekt sein für aufgabe9.2, oder?

...
Beinahe! Ein paar Flüchtigkeitsfehler:
...


Ja, das kommt, weil ich die Zeilen beim abtippen mit Copy&Paste gemacht... :)

Quoted

Original von Spike
Edit: Auweia, jetzt hab ich selbst noch was vergessen. Das leere Wort muss auch akzeptiert werden (warum?). Deshalb fehlt noch der Befehl

z1,#,# -> z4,#,#,N,N


war das "(warum?)" eine frage an dich selbst, oder an mich?
also, ich dachte bisher, dass wenn da w € {0,1}* steht, dann ist epsilon nicht enthalten. aber wahrscheinlich bedeutet * dass es auch nix sein kann, also leeres wort, dann wäre es ja klar.

Cipher

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

76

Tuesday, February 11th 2003, 7:41pm

Quoted

Original von Cipher

Quoted

Original von Spike
Edit: Auweia, jetzt hab ich selbst noch was vergessen. Das leere Wort muss auch akzeptiert werden (warum?). Deshalb fehlt noch der Befehl

z1,#,# -> z4,#,#,N,N


war das "(warum?)" eine frage an dich selbst, oder an mich?
also, ich dachte bisher, dass wenn da w € {0,1}* steht, dann ist epsilon nicht enthalten. aber wahrscheinlich bedeutet * dass es auch nix sein kann, also leeres wort, dann wäre es ja klar.

Cipher



Das war eine Frage an dich ;)

Das * bedeutet (und ich glaube, das wurde in der Vorlesung auch explizit erwähnt) dass das leere Wort dabei ist. Das hochgestellte + bedeutet, dass das leere Wort nicht dabei ist.

Cipher

Junior Schreiberling

  • "Cipher" is male

Posts: 156

Date of registration: Oct 15th 2002

Location: Berlin

Occupation: IT Application Consultant

77

Tuesday, February 11th 2003, 9:30pm

Frage zu Üb7 A1:

L = { a^nb^nc^m | n,m >= 1 }

würde es auch ausreichen eine Produktion anzugeben, die die Sprache erzeugt um dann daraus auf den Typ zu schließen ?

Beispiel:

G = { (B,D,S) , (a,b,c) , P , S}
mit P = {S->aBD, B->b, B->aBb, D->cD, D->c}
daraus folgt, dass G Typ 2 ist.


Cipher

sr409

Junior Schreiberling

Posts: 156

Date of registration: Jan 3rd 2003

78

Tuesday, February 11th 2003, 9:41pm

Ich has mit dem Pumping Lemma bewiesen dass es nicht regulär ist und dann n PDA geschrieben, der zeigt dass es Kontextfrei ist.

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

79

Tuesday, February 11th 2003, 9:44pm

Quoted

Original von Cipher
Frage zu Üb7 A1:

L = { a^nb^nc^m | n,m >= 1 }

würde es auch ausreichen eine Produktion anzugeben, die die Sprache erzeugt um dann daraus auf den Typ zu schließen ?
Kommt drauf an. Wenn nach der kleinsten Sprachklasse gefragt ist, dann mußt Du noch zeigen, daß die Sprache zu keiner kleineren Sprachklasse gehört (also z. B. durch Anwendung des Pumping-Lemmas).

Für Dein Beispiel bedeutet das, daß Du noch zeigen mußt, daß die Sprache nicht regulär ist (also, daß es keine zugehörige Typ-3-Grammatik gibt).

Ist hingegen in der Aufgabe nicht nach der kleinsten, sondern irgendeiner Sprachklasse gefragt, würde das wohl ausreichen (wenn man davon ausgeht, daß die Angabe einer Grammatik als Beweis genügt). Du solltest aber noch ein paar Zeilen Erklärung zu der Grammatik schreiben.

Quoted

Beispiel:

G = { (A,B,C,D,S) , (a,b,c) , P , S}
mit P = {S->aA, A->BD, B->b, B->aBC, C->b, D->cD, C->c}
daraus folgt, dass G Typ 2 ist.
Die letzte Produktion müßte D->c lauten, sonst ist das in Ordnung (kann man aber noch optimieren).
The purpose of computing is insight, not numbers.
Richard Hamming, 1962

Spike

Trainee

  • "Spike" is male

Posts: 41

Date of registration: Nov 8th 2002

Location: Würzburg

80

Tuesday, February 11th 2003, 9:46pm

Quoted

Original von Cipher
Frage zu Üb7 A1:

L = { a^nb^nc^m | n,m >= 1 }

würde es auch ausreichen eine Produktion anzugeben, die die Sprache erzeugt um dann daraus auf den Typ zu schließen ?

Beispiel:

G = { (B,D,S) , (a,b,c) , P , S}
mit P = {S->aBD, B->b, B->aBb, D->cD, D->c}
daraus folgt, dass G Typ 2 ist.


Cipher



Nein, mit der Angabe dieser Typ-2-Grammatik für L hast du gezeigt, dass L vom Typ 2 ist. Daraus folgt, dass sie vom Typ 1 und vom Typ 0 ist, aber es ist noch keine Aussage darüber getroffen worden, ob sie vom Typ 3 ist.

Jede Typ-3-Sprache ist nämlich auch vom Typ 2. D.h. man kann für jede Typ-3-Sprache eine Typ-2-Grammatik angeben. Aber nicht jede Typ-2-Sprache ist vom Typ 3. L ist z.B. nicht vom Typ 3. Aber das musst du erst beweisen.