Konstruktion einer TM < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:50 Do 10.12.2009 | | Autor: | mangaka |
| Aufgabe | Konstruieren Sie eine Turingmaschine [mm] $\Gamma$ [/mm] über dem Eingabealphabet [mm] $\Sigma=\{a,b\}$, [/mm] die niemals einen Schritt nach links macht und folgende Resultatsfunktion besitzt:
[mm] $h_{\Gamma}(w)=\begin{cases} a, & \mbox{ falls für alle Präfixe v von w stets } \#_a(v) -2 \leq \#_b(v) \leq \#_a(v)+2 \mbox{ gilt} \\ b, & \mbox{sonst} \end{cases} [/mm] |
Hi,
Wir sitzen schon seit fast 2 Stunden an der Aufgabe, haben aber keinen Ansatz.
Unser Problem ist, dass wir nicht wissen, wie man die Anzahl an as und bs bestimmen soll ohne jemals einen Schritt nach links zu machen.
Hätte jemand einen Ansatz für die Aufgabe?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:57 Sa 12.12.2009 | | Autor: | muy |
Ehehehe...Uni Oldenburg? Matthias? xD
Was man macht ist folgendes:
Zustände schaffen, die sich merken wie groß der Unterschied zwischen #a(v) und #b(v) ist, also
- 2 b mehr als a
- 1 b mehr
- gleich viele a und b
- 1 a mehr als b
- 2 a mehr
- ein Zustand für 3 a mehr als b oder andersherum, aus welchem man nicht mehr heraus kommt, weil hiermit ein Präfix existiert, der die Bedingungen für die Ausgabe eines a nicht mehr erfüllt.
Auf dem Weg von links nach rechts löscht man natürlich alle gelesenen Zeichen und schreibt dann ein a oder b, wenn das Wort zuende ist.
Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:21 So 13.12.2009 | | Autor: | mangaka |
Ha ha - Hallo Kommilitone :D Ich aber nix Mathias ...
Vielen Dank für den Tipp!
Wir haben den Automaten nun geschafft zu konstruieren.
Wir hatten auch am Anfang das Problem, dass wir nicht wussten, ob das Präfix auch das gesamte Wort sein kann. In diesem Fall geht man wohl davon aus.
Bis zum nächsten mal.
|
|
|
|
