Turingmaschine aus DFA konstruieren

Question

Aufgabe:

Sei \( M=\left(\Sigma, Z, \delta, z_{0}, F\right) \) ein DFA. Konstruieren Sie eine deterministische Turingmaschine \( M^{\prime}=\left(\Sigma, \Gamma, Z^{\prime}, \delta^{\prime}, z_{0}^{\prime}, \square, F^{\prime}\right) \) mit \( L(M)=L\left(M^{\prime}\right) \).

Ansatz/Problem:

Turingmaschinen sind mir ein Begriff, aber ich weiß nicht so recht was hier verlangt wird und wie ich vorgehen soll.

Answer 1

Sei \( M=\left(\Sigma, Z, \delta, z_{0}, F\right) \) ein DFA.

Informiere dich darüber, was \(\Sigma\), \(Z\), \(\delta\), \(z_0\) und \(F\) sind und wie der DFA für jedes \(\omega\in \Sigma^*\) entscheidet, ob \(\omega\in L(M)\) ist oder nicht.

eine deterministische Turingmaschine \( M^{\prime}=\left(\Sigma, \Gamma, Z^{\prime}, \delta^{\prime}, z_{0}^{\prime}, \square, F^{\prime}\right) \) mit \( L(M)=L\left(M^{\prime}\right) \)

Gib an, was \(\Gamma\), \(Z^\prime\), \(\delta^\prime\), \( z_{0}^{\prime}\), \(\square\) und \(F^{\prime}\) sein sollen, so dass \(L(M') = L(M)\) ist.

Comments

DFA:

Σ: ein Alphabet

Z: eine endliche Menge von Zustanden mit Σ ∩ Z = ∅

δ : Z × Σ → Z die Überfuhrungsfunktion

z0 ∈ Z der Startzustand

F ⊆ Z die Menge der Endzustande (Finalzustände).

Der DFA entscheidet für jedes w ∈ Σ* ob es in der Sprache liegt, indem der Automat prüft ob das Wort in einem Finalzustand endet.

Kommen wir jetzt zur Turngmaschine:

Z´: vermute ich mal die selben Zustände wie beim DFA und zusätzlich einen Endzustand für die Turingmaschine? Also: Z´:Z U {ze} ?

F´ wäre dann ja auch einfach, nämlich : {ze}.

Z0´ wäre dann immernoch Z0 würde ich vermuten. Σ bleibt unverändert.

Fehlen noch \(\Gamma\) \(\delta^\prime\) und \(\square\) , was auch immer man zum blank Symbol  angeben kann? Ist das bis hierhin richtig und wie kann ich weiter verfahren?

---

Z´: vermute ich mal die selben Zustände wie beim DFA und zusätzlich einen Endzustand für die Turingmaschine? Also: Z´:Z U {ze} ?

Ja.

F´ wäre dann ja auch einfach, nämlich : {ze}.

Ja.

Z0´ wäre dann immernoch Z0

Ja.

Σ bleibt unverändert.

Das ist in der Aufgabe so verlangt, weil \(\Sigma\) sowohl in \(M\), als auch in \(M'\) vorkommt.

Fehlen noch \(\Gamma\) \(\delta^\prime\) und \(\square\) ,

zu \(\Gamma\) und \(\square\):

\(\Gamma\) ist das Bandalphabet. Es ist \(\Sigma \subseteq \Gamma\) und \(\square\in \Gamma\setminus\Sigma\). Sei deshalb o.B.d.A \(\square\notin \Sigma\) und \(\Gamma = \Sigma\cup \{\square\}\).

zu \(\delta^\prime\):

Es ist

        \(\delta:\ Z\times \Sigma\to Z\)

aber

        \(\delta':\ Z'\times \Gamma\to Z'\times \Gamma\times \{L,N,R\}\).

Angenommen der Automat verfügt über eine Transition

        \(\delta(z_i, s) = z_j\).

Was sollte dann \(\delta'(z_i, s)\) sein? Beachte dabei, dass eine Turingmaschine im Gegensatz zu einem Automaten nach der Verarbeitung eines Zeichen

• nach links gehen kann,
• auf der aktuellen Bandposition bleiben kann,
• nach rechts gehen kann.

Es wäre gut, wenn man der Turingmaschine \(M'\) diese Möglichkeit nimmt.

Außerdem müssen wir uns noch um die Akzeptierung des Wortes kümmern. Woran könnte die Turingmaschine erkennen, dass das gesamte Wort gelesen wurde? Wie wird dann entschieden, ob in den akzeptierenden Zustand übergegangen werden soll oder nicht?

---

Ich tue mir schwer, weil wir kein Σ gegeben haben.

Die Akzeptierung des Wortes werden wir mit ze lösen. Stellt sich die Frage wann wir in den Fall kommen, ich muss ja in irgendeiner Form wissen was eingegeben werden kann. Dann könnte ich z.B. sagen: \(\delta^\prime\) = (z1, \(\square\) ) = (ze, \(\square\) , N). Aber wie soll ich zu z1 kommen oder soll man einfach direkt von z0 in den Endzustand...

---

Ich tue mir schwer, weil wir kein Σ gegeben haben.

Welchen Nutzen versprichst du dir davon, zu wissen dass zum Beispiel \(\Sigma = \{a,b,c,d,e\}\) ist?

\(\delta^\prime\) = (z1, \(\square\) ) = (ze, \(\square\) , N)

Ich glaube du meinst

        \(\delta^\prime(z_1, \square ) = (z_e, \square , N)\)

Dann würde das Wort akzeptiert werden. Unter welchen Bedingungen sollte ein solcher Übergang existieren?

Tipp. Welchen Teil von \( M=\left(\Sigma, Z, \delta, z_{0}, F\right) \) hast du denn noch nicht verwendet?

Aber wie soll ich zu z1 kommen

Ich zitiere aus meinem vorhergehende Kommentar:

Es ist

        \(\delta:\ Z\times \Sigma\to Z\)

aber

         \(\delta':\ Z'\times \Gamma\to Z'\times \Gamma\times \{L,N,R\}\).

Angenommen der Automat verfügt über eine Transition

        \(\delta(z_i, s) = z_j\).

Was sollte dann \(\delta'(z_i, s)\) sein?

---

Ich hätte einen Vorschlag:

\(\delta^\prime(z_1, 1 ) = (z_0, 1, R)\)

\(\delta^\prime(z_1, \square ) = (z_e, \square , N)\)

\(\delta^\prime(z_0, 0 ) = (z_1, 0 , R)\)

\(\delta^\prime(z_e, \square ) = (z_e, \square , N)\)

Sicher bin ich mir aber nicht.

---

\(\delta'(z,s) = (\delta(z,s), s, R)\) für jedes \(z\in Z\) und jedes \(s\in \Sigma\)

\(\delta'(z,\square) = (z_e, \square, N)\) für jedes \(z\in F\)

---

Danke dir...

Würde das was du geschrieben hast schon ausreichen oder ist zusätzlich meine Lösung nötig?

---

\(\delta^\prime(z_1, 1 ) = (z_0, 1, R)\)

Das ergibt keinen Sinn wenn \(z_1 \notin Z'\) ist.

Das ergibt keinen Sinn wenn \(1 \notin \Sigma\) ist.