Turing Maschine < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:04 Di 10.02.2009 | | Autor: | Yas |
Hallo zusammen, ich brauche hilfe mit diese frage !
Sei L = {w $ [mm] w^R [/mm] | w{a, b}*}, wobei [mm] w^R [/mm] das rückwärts notierte Wort w ist.
1. Geben Sie eine deterministische 1-Band TM [mm]M_1 [/mm] an, die L akzeptiert und auf allen Eingaben hält.
2. Geben Sie die Anzahl der von [mm]M1[/mm] ausgeführten Schritte in Abhängigkeit der Eingabelänge an.
so meine frage ist wie kann ich die ergebniss speichern? Ich fange von der erste simbol auf dem band, dann gehe ich Rechts bis ich Dollar sign finde danach wie kann ich speichern die symbole, die nach die Dollar sign kommt???
kann mir jemand hilfen??
Danke!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:42 Do 12.02.2009 | | Autor: | bazzzty |
> Hallo zusammen, ich brauche hilfe mit diese frage !
>
> Sei [mm]L = \{w \$ w^R | w\in\{a, b\}^\star\}[/mm], wobei [mm]w^R[/mm] das rückwärts
> notierte Wort w ist.
>
> 1. Geben Sie eine deterministische 1-Band TM [mm]M_1[/mm] an, die L
> akzeptiert und auf allen Eingaben hält.
>
> 2. Geben Sie die Anzahl der von [mm]M1[/mm] ausgeführten Schritte in
> Abhängigkeit der Eingabelänge an.
>
> so meine frage ist wie kann ich die ergebniss speichern?
Das "Ergebnis" bei einer Turing-Maschine ist im Zustand kodiert, in dem die Maschine anhält. Es gibt Finalzustände (in denen die Maschine hält) und darunter akzeptierende, d.h. "JA"-Finalzustände, und nicht-akzeptierende "NEIN"-Zustände. Mehr gibt es nicht zu speichern.
> Ich fange von der erste simbol auf dem band, dann gehe ich
> Rechts bis ich Dollar sign finde danach wie kann ich
> speichern die symbole, die nach die Dollar sign kommt???
> kann mir jemand hilfen??
Tja, so eine Turing-Maschine ist nicht so einfach. Man kann sich nicht viel "merken". Es wird auch nicht reichen, einmal über den ersten und einmal über den zweiten Teil zu laufen. Ich kann Dir aber mal eine mögliche Lösung (es gibt viele!) erklären, und Du versuchst das in einer Turing-Maschine zu kodieren:
1. Gehe vor bis zum (ersten) Dollarzeichen.
2. Lies das Zeichen davor, merke es Dir und überschreibe mit einem Dollarzeichen.
3. Gehe bis zum letzten Dollarzeichen.
4. Lies das Zeichen, vergleiche mit dem gemerkten, überschreibe mit einem Dollarzeichen. Ist es ungleich, halte nichtakzeptierend. Sonst gehe zurück zum ersten Dollarzeichen und mache bei "2." weiter.
Was fehlt noch zum Akzeptieren? Welcher Schritt muss verändert werden?
Kannst Du eine solche Turing-Maschine beschreiben?
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 10:39 Do 12.02.2009 | | Autor: | Yas |
> 2. Lies das Zeichen davor, merke es Dir und überschreibe
> mit einem Dollarzeichen.
genau das moechte ich wissen wenn ich jetzt zum bsp. ein "a" gelesen habe wie kann ich dieses "a" merken? brauche ich stack?
> Was fehlt noch zum Akzeptieren? Welcher Schritt muss
> verändert werden?
wie meinst du?
> Kannst Du eine solche Turing-Maschine beschreiben?
normale weise schon :P
>
danke!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:25 Do 12.02.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 11:19 Do 12.02.2009 | | Autor: | Yas |
Ich bin sooo doof (sorry) das ist doch einfach zu bemerken ob ein a oder b gelesen worden, durch schritte!!! Also schritt [mm] S_a [/mm] bzw. [mm] S_b [/mm] wenn ich ein a bzw. b gelesen habe.
> Was fehlt noch zum Akzeptieren? Welcher Schritt muss
> verändert werden?
das habe ich nicht verstanden! was meinst du da mit?kannst du vielleicht erklehren?
danke!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:25 Do 12.02.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Frage) überfällig | | Datum: | 13:43 Do 12.02.2009 | | Autor: | Yas |
> Was fehlt noch zum Akzeptieren? Welcher Schritt muss
> verändert werden?
Was heisst das?
> Kannst Du eine solche Turing-Maschine beschreiben?
Ja habe ich, ist das richtig?
$=d
a b d Blanck
S0 S0,a,R S0,b,R S1,d,L Sl,blanck,R
S1 Sa,d,R Sb,d,R S1,d,L Ja,blanck,N
Sa S1,d,L Nein,b,N Sa,d,R ------
Sb Nein,a,N S1,d,L Sb,d,R ---------
Sl Nein,a,N Nein,b,N Sl,dollar,R Ja,blanck,N
2. teil des Frage ist mir jetzt wichtig!!!
Danke!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:20 Do 12.02.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
