¿Cómo demostrar que una gramática es inequívoca?

25

Mi problema es cómo puedo probar que una gramática no es ambigua. Tengo la siguiente gramática:

Sstatementif expression then Sif expression then S else S

y hacer esto con una gramática inequívoca, creo que es correcto:

  • SS1S2

  • S1if expression then Sif expression then S2 else S1

  • S2if expression then S2 else S2statement

Sé que una gramática inequívoca tiene un árbol de análisis por cada término.

usuario1594
fuente

Respuestas:

20

Hay (al menos) una manera de demostrar falta de ambigüedad de una gramática para el lenguaje L . Consiste en dos pasos:G=(N,T,δ,S)L

  1. Demuestre .LL(G)
  2. Demuestre .[zn]SG(z)=|Ln|

El primer paso es bastante claro: demuestre que la gramática genera (al menos) las palabras que desea, eso es lo correcto.

El segundo paso muestra que tiene tantos árboles de sintaxis para palabras de longitud n como L tiene palabras de longitud n , con 1. esto implica falta de ambigüedad. Utiliza la función de estructura de G que se remonta a Chomsky y Schützenberger [1], a saberGnLnG

SG(z)=n=0tnzn

con el número de árboles de sintaxis que G tiene para palabras de longitud n . Por supuesto que necesitas tener | L n | para que esto funcionetn=[zn]SG(z)Gn|Ln|

Lo bueno es que es (generalmente) fácil de obtener para lenguajes libres de contexto, aunque encontrar una forma cerrada para t n puede ser difícil. Transforme G en un sistema de ecuaciones de funciones con una variable por no terminal:SGtnG

[A(z)=(A,a0ak)δ i=0k τ(ai) :AN] with τ(a)={a(z),aNz,aT.

Esto puede parecer desalentador, pero en realidad es solo una transformación sintáctica, como quedará claro en el ejemplo. La idea es que los símbolos terminales generados se cuentan en el exponente de y debido a que el sistema tiene la misma forma que G , z n ocurre con tanta frecuencia en la suma que G puede generar n terminales . Verifique Kuich [2] para más detalles.zGznnG

Resolver este sistema de ecuaciones (¡álgebra computacional!) Produce ; ahora "solo" tiene que extraer el coeficiente (en forma cerrada y general). La TCS Cheat Sheet y el álgebra computacional a menudo pueden hacerlo.S(z)=SG(z)


Ejemplo

Considere la gramática simple con reglasG

.SaSabSbε

Está claro que (paso 1, prueba por inducción). Hay 2 nL(G)={wwRw{a,b}} palíndromos de longitudnsines par,0 de locontrario.2n2nn0

Configurar el sistema de ecuaciones produce

S(z)=2z2S(z)+1

cuya solución es

.SG(z)=112z2

Los coeficientes de coinciden con el número de palíndromos, por lo que G no es ambiguo.SG G


  1. La teoría algebraica de los lenguajes sin contexto por Chomsky, Schützenberger (1963)
  2. Sobre la entropía de los lenguajes sin contexto por Kuich (1970)
Rafael
fuente
3
Como sabes @Raphael, la ambigüedad no es decidible, por lo que al menos uno de tus pasos no se puede mecanizar. ¿Alguna idea de cuáles? ¿Obtener un formulario cerrado para ? tn
Martin Berger
2
El sistema de ecuaciones puede no ser solucionable algorítmicamente si el grado es demasiado alto, y extraer los coeficientes exactos de las funciones generadoras puede ser (demasiado) difícil. Sin embargo, en la "práctica", a menudo se trata de gramáticas de pequeño "grado" - tenga en cuenta que, por ejemplo, la forma normal de Chomsky conduce a sistemas de ecuaciones de pequeño grado - y hay métodos para obtener al menos -asintóticos para los coeficientes ; Esto puede ser suficiente para establecer la ambigüedad. Tenga en cuenta que para demostrar la no ambigüedad, es suficiente mostrar S L ( z ) = S G ( z ) sin coeficientes de tracción; Sin embargo, probar esta identidad puede ser difícil. SL(z)=SG(z)
Rafael
Gracias @Raphael. ¿Conoces algún texto que desarrolle en detalle cómo entra en juego la indecidibilidad incluso si se usa, por ejemplo, la forma normal de Chomsky? (No puedo contactar a Kuich.)
Martin Berger
@ MartinBerger Acabo de redescubrir su comentario en mi lista de tareas pendientes; Lo siento por el prolongado silencio. Hay tres pasos que (pienso) no son computables en general: 1) Determinar . 2) Calcular | L n | . 3) Determine [ z n ] S g ( z ) . En particular, ¿qué representación de L usar para 2)? SG|Ln|[zn]Sg(z)L
Raphael
LLn
6

Esta es una buena pregunta, pero algunos Google le habrían dicho que no existe un método general para decidir la ambigüedad , por lo que debe hacer su pregunta más específica.

reinierpost
fuente
2
El OP solicita técnicas de prueba, no algoritmos.
Raphael
Yo también lo creo; podría mencionarse en la pregunta.
reinierpost
1
Google no es un oráculo de la verdad, porque knowlede no es democrático, y los resultados de Google sí lo son. No contaría con Google en este caso, porque las personas a menudo copian uno del otro sin verificar la exactitud de lo que copian. Sin mostrar una prueba, podrían estar equivocados.
SasQ
55
@SasQ: Lees mis palabras demasiado literalmente. Lo que Google me da son las URL de los artículos que explican las cosas.
reinierpost
4

Para algunas gramáticas, es posible una prueba por inducción (sobre la longitud de la palabra).


GΣ={a,b}

SaSabSbε

1L(G)ε

nnN

w=w1wwnL(G)Σnn>0w1Σw1=aSaSaw1=bSbSbww


Esto se vuelve más difícil si

  • hay múltiples no terminales,
  • la gramática no es lineal y / o
  • la gramática es recursiva a la izquierda.

Puede ayudar a fortalecer el reclamo de todas las formas de sentencia (si la gramática no tiene no terminales no productivos) y no terminales "raíz".

Creo que la conversión a la forma normal de Greibach mantiene (una) ambigüedad, ya que aplicar este paso primero puede encargarse de la recursión izquierda muy bien.

La clave es identificar una característica de cada palabra que corrige (al menos) un paso de derivación. El resto sigue inductivamente.

Rafael
fuente
3

Básicamente, es un problema de generación infantil. Comience con la primera expresión y genere sus hijos ... Siga haciéndolo recursivamente (DFS), y después de varias iteraciones, vea si puede generar la misma expresión expandida a partir de dos hijos diferentes. Si puede hacer eso, es ambiguo. Sin embargo, no hay forma de determinar el tiempo de ejecución de este algoritmo. Suponga que es seguro, después de quizás generar 30 niveles de niños :) (Por supuesto, podría bombardear el 31)

Karthik Kumar Viswanathan
fuente
1
El OP solicita técnicas de prueba, no algoritmos.
Raphael
2
eso no puede ser una forma de demostrar si una gramática es ambigua o no. De hecho, cuando ocurre ese bombardeo es indecidible.
Sanađошƒаӽ