Turing Maschine (NDTM) < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Schreiben Sie ein Programm für eine nicht deterministische Turing Maschine, welche eine Zufallszahl zwischen 0 und 10 erzeugt |
Ich weiß, dass bei einer nicht deterministischen Turing Maschine (NDTM) es mehrere Übergänge geben kann, da die Zustandsübergangsfunktion [mm] \delta [/mm] durch eine Relation ersetzt wurde.
Ich verstehe jetzt nur nicht ganz wie ich Anfangen soll ein Programm, wie in der Aufgabenstellung gewünscht, zu konstruieren.
Ich würde jetzt irgendwie so anfangen, dass die NDTM das erste Zeichen mit 0 oder 1 rät.
Da die Wertigkeit der Zahlen die erzeugt werden kann binär durch 4 Stellen dargestellt werden kann, weiß ich wenn eine 1 erraten wurde eine 0 folgen muss, da sonst der obere Wert überschritten wird. Hier müsste die NDTM ja beim raten einer 1 an Position 2 in einen Fehlerzustand kommen.
Wenn die NDTM eine 0 geraten hat können die nächsten 3 Stellen beliebig von der NDTM mit 0 oder 1 geraten werden ohne in einen Fehlerzustand zu kommen.
Vielleicht kann mir jemand sagen ob der Ansatz einigermaßen richtig ist und wie das ganze Raten am besten aufgeschrieben wird. Werden einfach beide Möglichkeit in der Tabelle in einem Zustand übernommen oder wird es anders aufgeschrieben?
Ich habe irgendwie das Gefühl, ich gehe viel zu sehr deterministisch vor.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:17 Di 10.09.2013 | | Autor: | canogretic |
Ich würde das ganze jetzt in folgender Tabelle aufstellen:
| State |
Letter |
|
State' |
letter' |
Bewegung |
| q0 |
B |
|
q1 |
1 |
R |
| q0 |
B |
|
q1 |
0 |
R |
| q1 |
B |
|
q2 |
0 |
R |
| q1 |
B |
|
qe |
1 |
- |
| q2 |
B |
|
q3 |
1 |
R |
| q2 |
B |
|
q3 |
0 |
R |
| q3 |
B |
|
q4 |
1 |
R |
| q3 |
B |
|
q4 |
0 |
R |
| q4 |
B |
|
q5 |
B |
L |
| q5 |
0 |
|
q5 |
0 |
L |
| q5 |
1 |
|
q5 |
1 |
L |
| q5 |
B |
|
q6 |
B |
R |
| q6 |
1 |
|
q6 |
1 |
N |
| q6 |
0 |
|
q6 |
0 |
N |
| qe |
* |
|
qe |
* |
N |
Kann mir evtl. jemand mitteilen ob der Ansatz an sich einigermaßen korrekt ist oder ob grundlegend daran etwas falsch ist.
In dem Fall der Tabelle wäre q6 der akzeptierende Zustand und qe der Fehlerzustand.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 Fr 13.09.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
