Gibt es eine einfache Möglichkeit, Fragen wie "Konstruieren Sie eine Turing-Maschine ..." zu lösen?

Question

Ich habe die Logik der Turing-Maschine verstanden. Wenn die Turing-Maschine gegeben ist, kann ich verstehen, wie sie funktioniert und wie sie anhält. Aber wenn ich gefragt werde eine Turing-Maschine zu konstruieren, ist es schwieriger.

Gibt es eine einfache Möglichkeit, die Antwort auf Fragen zu finden wie:

Construct a Turing machine a*b* 
Construct a Turing machine a*b*a* 
etc.

Ich möchte ein Diagramm dieser Turing-Maschine? Gibt es irgendeine Methode, wie z.B. Tabellen ausfüllen und dann als Diagramm darstellen, usw.?

Ich habe im Internet viel über dieses Thema recherchiert. Es gibt nur Antworten (nur Diagramme). Es gibt keine Erklärung, wie es gelöst wird, wie es schematisch dargestellt ist.

Vielen Dank im Voraus

Answer 1

Bei den beiden von Ihnen genannten Beispielen handelt es sich um reguläre Ausdrücke, und es gibt in der Tat einfache algorithmische Möglichkeiten, reguläre Ausdrücke in Automaten umzuwandeln - nämlich in NFAs. Sobald man NFAs hat, kann man sie mit einer einfachen Konstruktion in TMs umwandeln.

Der Algorithmus zur Umwandlung von regulären Ausdrücken in NFAs sieht folgendermaßen aus:

Regel 1: Wenn r = a für ein Alphabet-Symbol a, dann ist die NFA für r ist:

       a
--->q0--->(q1)

Regel 2: Wenn r = st für reguläre Ausdrücke s, t y M1 y M2 sind NFAs für s y t dann ist die NFA für r ist:

       e
--->M1--->M2

Das heißt, der Ausgangszustand ist der von M1 sind die akzeptierenden Zustände diejenigen von M2 , und es gibt neue leere Übergänge von allen (ehemals) akzeptierenden Zuständen von M1 auf den (früheren) Ausgangszustand von M2 .

Regel 3: wenn r = s + t für reguläre Ausdrücke s, t y M1 y M2 sind NFAs für s y t dann ist die NFA für r ist:

       e
--->q0--->M1
     | e
     +--->M2

Das heißt, der Ausgangszustand ist ein neuer Zustand q0 sind die Endzustände die der beiden M1 y M2 und es werden zwei leere Übergänge hinzugefügt, die vom neuen Ausgangszustand zu den (früheren) Ausgangszuständen der beiden M1 y M2 .

Regel 4: Wenn r = s* für reguläre Ausdrücke s y M ist ein NFA für s dann eine NFA für r ist:

     +------+
     |  e   |
     V      |
--->(q0)--->M

Das heißt, ein neuer Ausgangszustand q0 hinzugefügt wird, sind die akzeptierenden Zustände diejenigen von M zusammen mit q0 und es werden neue leere Übergänge aus den akzeptierenden Zuständen von M a q0 .

In Ihren Beispielen leiten wir die NFAs wie folgt ab:

a: Rule 1           a
             --->q0--->(q1)

b: Rule 1           b
             --->q0--->(q1)

a*: Rule 4         +-------------+
                   |      e      |
                   V             |
             --->(q0)--->q0'--->(q1)
                      e      a

b*: Rule 4         +-------------+
                   |      e      |
                   V             |
             --->(q0)--->q0'--->(q1)
                      e      b

a*b*: Rule 2      +-----------+
                  |           | e
                  V e      a  |
             --->q0--->q0'--->q1
                  |           |
                e |           | e
                  +-----------+--+
                  |              | e
                  V   e      b   |
                 (q2)--->q2'--->(q3)

a*b*: Rule 2      +-----------+
                  |           | e
                  V e      a  |
             --->q0--->q0'--->q1
                  |           |
                e |           | e
                  +-----------+
                  |           | e
                  V  e    b   |
                 q2--->q3'--->q3
                  |           |
                e |           | e
                  +-----------+--+
                  |              | e
                  V   e      a   |
                 (q4)--->q5'--->(q5)

Mit einem NFA in der Hand kann ein TM wie folgt konstruiert werden:

1. Dieselben Staaten wie die NFA
2. Übergänge, die einen Eingang verbrauchen, bewegen den Bandkopf nach rechts.
3. Bei leeren Übergängen wird der Bandkopf überhaupt nicht bewegt.
4. Der TM überschreibt niemals seine Eingabe.
5. Wenn der TM auf ein Leerzeichen stößt, nachdem er sich weit genug nach rechts bewegt hat, geht er in den Zustand "halt-accept" über, wenn er sich in einem akzeptierenden Zustand für den DFA befindet, und andernfalls in den Zustand "halt-reject".