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

9

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 ".{ 0 , 1 , ¯ 0 , ¯ 1 } P ¯ 0 0 ϵ ¯ 1 1 ϵ G P G Psol{0 0,1,0 0¯,1¯}PAGS0 0¯0 0ϵ1¯1ϵsolPAGSsolPAGS

¿Es posible dar un algoritmo que tome una gramática y una cadena over y decida si ? s { 0 , 1 , ¯ 0 , ¯ 1 } s L ( G P )solPAGSs{0 0,1,0 0¯,1¯}sL(solPAGS)

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 P ) L ( G ) L ( G P ) ϵ ( s , ϵ , t ) ( s , ˉ 0 , p , 0 , t ) , ( s , ˉ 0 , p , ϵ , q , 0 , t ) , ( s , ˉ 1L(sol)L(solPAGS)L(sol)L(solPAGS)ϵ(s,ϵ,t)( s , ϵ , p , ϵ , t ) ϵ(s,0 0¯,pags,0 0,t),(s,0 0¯,pags,ϵ,q,0 0,t),(s,1¯,pags,1,t),(s,1¯,pags,ϵ,q,1,t)(s,ϵ,pags,ϵ,t)ϵ
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. PAGS
Amit.

Respuestas:

5

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]

Aquí:

  • , después de aplicar P , solo contiene los caracteres ¯ 0 y ¯ 1 .[cinta a la izquierda]PAGS0 0¯1¯
  • , después de aplicar P , solo contiene los caracteres 0 y 1 .[tape to the right]P0 01
  • es un único no terminal, que codifica tanto el estado de la cabeza como el carácter en la posición de la cabeza.[cabeza]

Suponga que la cabeza está en estado , y el carácter debajo de la cabeza es i { 0 , 1 } . Entonces la cabeza está representada por S i 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 ySyo{0 0,1}SyoTjSyo0 0T0 0jSyo1T1jSyoj¯T0 00 0¯Syoj¯T11¯. 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.[cinta a la izquierda][cinta a la derecha]

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 N ? Pero mi problema solo permite dos producciones fijas sin restricciones. nortenorte
Amit.
@ Amit.SI proporcionó alguna explicación más de las transiciones en la respuesta.
abacabadabacaba