Problème d'adhésion pour certaines classes de grammaires illimitées

Considérons une grammaire arbitraire sans contexte sur l'alphabet { 0 , 1 , ¯ 0 , ¯ 1 } . Aux productions de cette grammaire, ajoutez deux productions fixes non contextuelles P : ¯ 0 0 → ϵ et ¯ 1 1 → ϵ . Appelons la grammaire résultante G P pour " G augmenté des productions P ".$G$$\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$$P$$\overline{0} 0 \rightarrow \epsilon$$\overline{1} 1 \rightarrow \epsilon$$G^P$$G$$P$

Est-il possible de donner un algorithme qui prend une grammaire et une chaîne s sur { 0 , 1 , ¯ 0 , ¯ 1 } et décide si s ∈ L ( G P ) ?$G^P$$s$$\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$$s \in \mathcal{L}(G^ P)$

Cette classe de grammaires est indécidable. Voici une idée approximative de la façon de l'utiliser pour émuler des machines Turing.

À chaque point, le mot partiellement développé actuel ressemblerait à

Ici:

• $[\mbox{tape to the left}]$$P$$\overline0$$\overline1$
• $[\mbox{tape to the right}]$$P$$0$$1$
• $[\mbox{head}]$

$S$$i\in\{0,1\}$$S_i$$T$$j$$S_i\rightarrow0T_0j$$S_i\rightarrow1T_1j$$S_i\rightarrow\overline jT_0\overline0$$S_i\rightarrow\overline jT_1\overline 1$$[\mbox{tape to the left}]$$[\mbox{tape to the right}]$

Lorsque la machine s'arrête, la tête doit "consommer" sa bande des deux côtés en "devinant" et en produisant des caractères correspondants. Après cela, il devrait produire un mot vide. En conséquence, un mot vide serait membre d'une telle grammaire si et seulement si la machine de Turing correspondante s'arrêtait.