Problema de associação para determinadas classes de gramáticas irrestritas

Considere uma gramática arbitrária e livre de contexto sobre o alfabeto . Nas produções desta gramática, adicione duas produções fixas sem contexto : e . Chame a gramática resultante de " aumentada com as produções ".{ 0 , 1 , ¯ 0 , ¯ 1 } P ¯ 0 0 → ϵ ¯ 1 1 → $G$$\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$$P$$\overline{0} 0 \rightarrow \epsilon$$\overline{1} 1 \rightarrow \epsilon$ G $G^P$$G$$P$

É possível fornecer um algoritmo que use uma gramática e uma string acima de e decida se ? s { 0 , 1 , ¯ 0 , ¯ 1 } s ∈ L ( $G^P$$s$$\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$$s \in \mathcal{L}(G^ P)$

Esta classe de gramáticas é indecidível. Aqui está uma idéia aproximada de como usá-lo para emular as máquinas de Turing.

Em cada ponto, a palavra parcialmente expandida atual pareceria

Aqui:

• P ¯ 0 ¯ $[\mbox{tape to the left}]$ , após aplicar , contém apenas caracteres e .$P$$\overline0$$\overline1$
• P 0 $[\mbox{tape to the right}]$ , após aplicar , contém apenas os caracteres e .$P$$0$$1$
• $[\mbox{head}]$ é um não-terminal único, que codifica o estado do cabeçalho e o caractere na posição do cabeçalho.

Suponha que a cabeça esteja no estado e o caractere embaixo dela seja . Então a cabeça é representada por não-terminal . Se precisar fazer a transição para o estado , substitua o caractere atual por e mova para a esquerda, existem duas transições e . Se precisar mover para a direita, existem duas transições ei ∈ { 0 , 1 } S i T j S i → 0 T 0 j S i → 1 T 1 j S i → ¯ j T 0 ¯ 0 S i → ¯ j T 1 ¯ 1 [ fita para a esquerda ] [ fita para a direita$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$. Em certo sentido, a cabeça precisa "adivinhar" o personagem na direção em que está se movendo, produzindo o caractere correspondente. Se o palpite estiver errado, o invariante em ou seria violado e nunca se recuperaria.$[\mbox{tape to the left}]$$[\mbox{tape to the right}]$

Quando a máquina pára, a cabeça deve "consumir" sua fita nos dois lados "adivinhando" e produzindo caracteres correspondentes. Depois disso, deve produzir palavra vazia. Como resultado, a palavra vazia seria membro dessa gramática se e somente se a máquina de Turing correspondente parar.