Fachrat Informatik - Forum

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 ?

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]

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

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

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

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:
...

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

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

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 ?

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.

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