Jak przekonwertować maszynę Turinga rozpoznającą język na nieograniczoną gramatykę?

Zgodnie z tym artykułem Wikipedii , nieograniczone gramatyki są równoważne maszynom Turinga. Artykuł zauważa, że ​​mogę przekonwertować dowolną maszynę Turinga na nieograniczoną gramatykę, ale pokazuje ona tylko, jak przekonwertować gramatykę na maszynę Turinga.

Jak rzeczywiście to zrobić i przekonwertować maszynę Turinga rozpoznającą język na nieograniczoną gramatykę? Próbowałem zastąpić reguły przejścia regułami gramatyki, ale maszyna Turinga może mieć również wiele różnych konfiguracji stanów ...$L$

Kodujemy zawartość taśmy maszyny Turinga w formie sentymentalnej; specjalny zestaw nie-terminali koduje aktualny stan. W dowolnym momencie może być tylko jeden z nich w formie sentymentalnej, umieszczony po prawej stronie symbolu, na który obecnie wskazuje TM.

Drugim kluczowym pomysłem jest to, że musimy odwrócić ten proces: TM biorą słowo jako dane wejściowe i przekształcają je w lub , w przeciwnym razie nie zakończą się. Gramatyka musi jednak generować słowo. Na szczęście gramatyki są z natury niedeterministyczne, więc możemy po prostu pozwolić „odgadnąć”, skąd pochodzi akceptująca ; wówczas mogą zostać wygenerowane wszystkie słowa, które powodują akceptację bazy TM.0 $1$$0$$1$

Niech zestaw stanów nieterminalnych; niech będzie początkowym stanem nieterminalnym, a zestawem stanów-przyjmujących-nieterminalnych. Po pierwsze, potrzebujemy reguł początkowych, które generują wszystkie możliwe konfiguracje akceptacji: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$ dla wszystkich .$Q_f \in \cal{Q}_F$

Podobnie kończymy, gdy „osiągniemy” stan początkowy we właściwej pozycji, a mianowicie na pierwszym symbolu:

$\qquad \#aQ_0 \to \#a \qquad$ dla wszystkich .$a \in \Sigma$

Tłumaczenie rzeczywistych przejść stanu jest proste:

$\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}$

Jest kilka technicznych problemów, które można rozwiązać; na przykład musisz pozbyć się znaczników granic na końcu. Można to zrobić, spawnując dwa specjalne nieterminale zamiast kończąc, zamieniając je na końce, a następnie usuwając wraz z nimi. Ponadto na żądanie trzeba utworzyć więcej ; wymaga to hakowania reguł za pomocą .$\#$$\#$$\#$$d=\#$

Ponadto konstrukcja staje się nieco bardziej skomplikowana, jeśli TM używa symboli niewprowadzanych. W takim przypadku reguły zakończenia mogą być niepoprawne: jeśli gdzieś na taśmie znajdują się symbole niewprowadzane, nie wygenerowaliśmy właściwego słowa. Można to naprawić podobnie do usuwania : spawn specjalnego -0 z terminalu, który jest zamieniany w prawo i usuwany tylko wtedy, gdy wszystkie symbole pochodzą z .$\#$$Q_0$$\Sigma$