Problema de membresía para cierta clase de gramáticas sin restricciones

Considere una gramática arbitraria sin contexto sobre el alfabeto . A las producciones de esta gramática, agregue dos producciones fijas sin contexto : y . Llame a la gramática resultante que significa " aumentada con las producciones ". $G$ $\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$ $P$ $\overline{0} 0 \rightarrow \epsilon$ $\overline{1} 1 \rightarrow \epsilon$ $G^P$ $G$ $P$

¿Es posible dar un algoritmo que tome una gramática y una cadena over y decida si ? $G^P$ $s$ $\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$ $s \in \mathcal{L}(G^ P)$

context-free decidability Amit S
fuente

Curiosamente, aunque la respuesta parece ser "no", creo que si es regular, entonces también lo es . Esencialmente, un NFA para se puede transformar en uno para agregando iterativamente -transitions siempre que tenga rutas o , y finalmente realizar -elimination.

L (G)

$L(G)$

L (G^{P})

$L(G^P)$

L (G)

$L(G)$

L (G^{P})

$L(G^P)$

ϵ

$\epsilon$

(s, ϵ, t)

$(s,\epsilon,t)$

(s, \bar{0}, p, 0, t), (s, \bar{0}, p, ϵ, q, 0, t), (s, \bar{1}, p, 1, t), (s, \bar{1}, p, ϵ, q, 1, t)

$(s,\bar{0},p,0,t),(s,\bar{0},p,\epsilon,q,0,t),(s,\bar{1},p,1,t),(s,\bar{1},p,\epsilon,q,1,t)$

(s, ϵ, p, ϵ, t)

$(s,\epsilon,p,\epsilon,t)$

ϵ

$\epsilon$

Klaus Draeger

Si eso es verdad. De hecho, la pregunta surgió de un problema en el análisis del programa (recolección de basura basada en la vida). Eludimos el problema al aproximar el CFG a una gramática fuertemente regular (transformación de Mohri-Nederhoff), y luego hacer las simplificaciones de en el NFA resultante exactamente de la manera en que Klaus Draeger menciona.

P

$P$

Amit.

Respuestas:

Esta clase de gramáticas es indecidible. Aquí hay una idea aproximada sobre cómo usarlo para emular máquinas Turing.

En cada punto, la palabra actual parcialmente expandida se vería como

[cinta a la izquierda] [cabeza] [cinta a la derecha]

$[\mbox{tape to the left}][\mbox{head}][\mbox{tape to the right}]$

Aquí:

, después de aplicar , solo contiene los caracteres y . $[\mbox{tape to the left}]$ $P$ $\overline0$ $\overline1$
, después de aplicar , solo contiene los caracteres y . $[\mbox{tape to the right}]$ $P$ $0$ $1$
es un único no terminal, que codifica tanto el estado de la cabeza como el carácter en la posición de la cabeza. $[\mbox{head}]$

Suponga que la cabeza está en estado , y el carácter debajo de la cabeza es . Entonces la cabeza está representada por no terminal . Si necesita pasar al estado , reemplazar el carácter actual con y moverse hacia la izquierda, hay dos transiciones y . Si necesita moverse hacia la derecha, hay dos transiciones y $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$ . En cierto sentido, la cabeza tiene que "adivinar" el personaje en la dirección en que se mueve produciendo el personaje correspondiente. Si la suposición es incorrecta, la invariante en o sería violada, y nunca se recuperaría. $[\mbox{tape to the left}]$ $[\mbox{tape to the right}]$

Cuando la máquina se detiene, la cabeza debe "consumir" su cinta en ambos lados "adivinando" y produciendo caracteres coincidentes. Después de eso, debería producir una palabra vacía. Como resultado, la palabra vacía sería miembro de dicha gramática si y solo si la máquina de Turing correspondiente se detiene.

abacabadabacaba
fuente

No estoy seguro de entender tu reducción. Aquí está mi duda: si la máquina de Turing dada tiene

estados, entonces ¿no es el número de producciones sin restricciones requeridas para emular la máquina de Turing relacionada con

? Pero mi problema solo permite dos producciones fijas sin restricciones.

N

$N$

N

$N$

Amit.

@ Amit.SI proporcionó alguna explicación más de las transiciones en la respuesta.

abacabadabacaba