Comment puis-je convertir la machine Turing la langue reconnue en une grammaire illimitée?

Selon cet article de Wikipedia , les grammaires illimitées sont équivalentes aux machines de Turing. L'article note que je peux convertir n'importe quelle machine Turing en une grammaire illimitée, mais il montre uniquement comment convertir une grammaire en machine Turing.

Comment puis-je vraiment faire cela et convertir la machine Turing le langage reconnu en une grammaire sans restriction? J'ai essayé de remplacer les règles de transition par des règles de grammaire, mais une machine de Turing peut également avoir de nombreuses configurations d'états différentes ...$L$

Nous encodons le contenu de la bande de la machine Turing sous des formes sententielles; un ensemble spécial de non-terminaux encode l'état actuel. Il ne peut y en avoir qu'un sous la forme sententielle à tout moment, placé à droite du symbole sur lequel la MT pointe actuellement.

La deuxième idée cruciale est que nous devons inverser le processus: les MT prennent le mot en entrée et le convertissent en ou 0 , ou ils ne se terminent pas. La grammaire, cependant, doit générer le mot. Heureusement, les grammaires sont intrinsèquement non déterministes, nous pouvons donc simplement le laisser «deviner» d'où vient le 1 acceptant ; tous les mots qui font accepter la MT peuvent alors être générés.$1$$0$$1$

Soit l'ensemble des états non terminaux; wlog laisse Q 0 être l'état de départ non terminal et Q F ⊆ Q l'ensemble des états d'acceptation non terminaux. Tout d'abord, nous avons besoin de règles de démarrage qui génèrent toutes les configurations d'acceptation possibles:$\cal{Q} = \{Q_0,\dots,Q_k\}$$Q_0$$\cal{Q}_F \subseteq \cal{Q}$

$\qquad \displaystyle S \to \#1Q_f\# \qquad$pour tous les .$Q_f \in \cal{Q}_F$

De même, nous terminons lorsque nous «atteignons» l'état de départ dans la position correcte, à savoir sur le premier symbole:

$\qquad \#aQ_0 \to \#a \qquad$pour tous .$a \in \Sigma$

La traduction des transitions d'état réelles est simple:

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

Il y a quelques problèmes techniques à régler; par exemple, vous devez vous débarrasser des bornes à la fin. Cela peut être fait en générant deux terminaux non spéciaux au lieu de terminer, en les échangeant aux extrémités, puis en supprimant le # avec eux. En outre, il faut créer plus de # sur demande; cela nécessite un piratage des règles avec d = # .$\#$$\#$$\#$$d=\#$

De plus, la construction devient un peu plus compliquée si le TM utilise des symboles non entrés. Dans ce cas, les règles de terminaison peuvent être erronées: s'il y a des symboles de non-entrée quelque part sur la bande, nous n'avons pas généré un mot correct. Cela peut être corrigé de manière similaire à la suppression de : engendre un non-terminal spécial de Q 0 qui est échangé vers la droite et supprimé uniquement si tous les symboles sont de Σ .$\#$$Q_0$$\Sigma$