Wie kann ich die Turing-Maschine der erkannten Sprache in eine uneingeschränkte Grammatik umwandeln ?

Laut diesem Wikipedia-Artikel entsprechen uneingeschränkte Grammatiken Turing-Maschinen. Der Artikel stellt fest, dass ich jede Turing-Maschine in eine uneingeschränkte Grammatik umwandeln kann, es wird jedoch nur gezeigt, wie man eine Grammatik in eine Turing-Maschine umwandelt.

Wie mache ich das und wandle die Turingmaschine die erkannte Sprache in eine uneingeschränkte Grammatik um? Ich habe versucht, Übergangsregeln durch Grammatikregeln zu ersetzen, aber eine Turing-Maschine kann auch viele verschiedene Zustandskonfigurationen haben ...$L$

Wir kodieren den Bandinhalt der Turing-Maschine in sententialen Formen. Ein spezieller Satz von Nicht-Terminals codiert den aktuellen Status. Es kann zu jedem Zeitpunkt nur eine davon in der sententialen Form geben, die rechts neben dem Symbol steht, auf das das TM gerade zeigt.

Die zweite wichtige Idee ist, dass wir den Prozess umkehren müssen: TMs nehmen das Wort als Eingabe und wandeln es in oder , oder sie enden nicht. Die Grammatik muss jedoch das Wort erzeugen. Glücklicherweise sind Grammatiken von Natur aus nicht deterministisch, so dass wir einfach davon ausgehen können, woher die akzeptierende stammt. Alle Wörter, die das TM akzeptieren lassen, können dann generiert werden.0 $1$$0$$1$

Es sei die Menge von Zustands-Nicht-Endpunkten; wlog Sei das Startzustands- Nicht-Endgerät und die Menge der Akzeptanzzustands-Nicht-Endgeräte. Zunächst benötigen wir Startregeln, die alle möglichen akzeptierenden Konfigurationen generieren:Q 0 Q F ⊆ $\cal{Q} = \{Q_0,\dots,Q_k\}$$Q_0$$\cal{Q}_F \subseteq \cal{Q}$

$\qquad \displaystyle S \to \#1Q_f\# \qquad$ für alle .$Q_f \in \cal{Q}_F$

Ebenso beenden wir, wenn wir den Ausgangszustand in der richtigen Position "erreichen", nämlich auf dem ersten Symbol:

$\qquad \#aQ_0 \to \#a \qquad$ für alle .$a \in \Sigma$

Das Übersetzen der tatsächlichen Zustandsübergänge ist einfach:

$\qquad \begin{align} aQ &\to cQ' \qquad\ \,\text{ for } a,c \in \Sigma \land (a,Q,N) \in \delta(c,Q') \\ aQb &\to acQ' \qquad \text{ for } a,b,c \in \Sigma \land (b,Q,L) \in \delta(c,Q') \\ abQ &\to cQ'b \qquad\, \text{ for } a,b,c \in \Sigma \land (a,Q,R) \in \delta(c,Q') \end{align}$

Es gibt einige technische Probleme, die behoben werden müssen. Zum Beispiel müssen Sie die Begrenzungsmarkierungen am Ende entfernen . Dies können Sie tun, indem Sie zwei spezielle Nichtterminals erzeugen, anstatt sie zu beenden, diese an die Enden tauschen und dann das mit ihnen entfernen . Darüber hinaus müssen mehr auf Anfrage erstellt werden; das erfordert einiges hacken der regeln mit .# # d = $\#$$\#$$\#$$d=\#$

Außerdem wird die Konstruktion etwas komplizierter, wenn das TM Symbole ohne Eingabe verwendet. In diesem Fall können die Beendigungsregeln falsch sein: Wenn sich irgendwo auf dem Band nicht eingegebene Symbole befinden, haben wir kein richtiges Wort generiert. Dies kann ähnlich wie das Entfernen von : Spawn eines speziellen Nicht-Terminals aus , das nach rechts vertauscht und nur dann entfernt wird, wenn alle Symbole aus .Q 0$\#$$Q_0$$\Sigma$