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

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

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

• $S → S_1 ∣ S_2$

• $S_1 → \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression \mbox{ then } S_2 \mbox{ else } S_1$

• $S_2 → \mbox{if } expression \mbox{ then } S_2 \mbox{ else } S_2 ∣ statement$

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

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,\delta,S)$$L$

1. Demuestre .$L \subseteq \mathcal{L}(G)$
2. Demuestre .$[z^n]S_G(z) = |L_n|$

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 saber$G$$n$$L$$n$$G$

$\qquad \displaystyle S_G(z) = \sum_{n=0}^\infty t_nz^n$

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 funcione$t_n = [z^n]S_G(z)$$G$$n$$|L_n|$

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:$S_G$$t_n$$G$

$\qquad \displaystyle \left[ A(z) = \sum\limits_{(A, a_0 \dots a_k) \in \delta} \ \prod\limits_{i=0}^{k} \ \tau(a_i)\ : A \in N \right] \text{ with } \tau(a) = \begin{cases} a(z) &, a \in N \\ z &, a \in T \\ \end{cases}.$

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.$z$$G$$z^n$$n$$G$

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) = S_G(z)$

Ejemplo

Considere la gramática simple con reglas$G$

.$\qquad \displaystyle S \to aSa \mid bSb \mid \varepsilon$

Está claro que (paso 1, prueba por inducción). Hay 2 $\mathcal{L}(G) = \{ww^R \mid w \in \{a,b\}^*\}$ palíndromos de longitudnsines par,0 de locontrario.$2^{\frac{n}{2}}$$n$$n$$0$

Configurar el sistema de ecuaciones produce

$\qquad \displaystyle S(z) = 2z^2S(z) + 1$

cuya solución es

.$\qquad \displaystyle S_G(z) = \frac{1}{1-2z^2}$

Los coeficientes de coinciden con el número de palíndromos, por lo que G no es ambiguo.$S_G$ $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)

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.

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

$G$$\Sigma = \{a,b\}$

$\qquad \displaystyle S \to aSa \mid bSb \mid \varepsilon$

$\leq 1$$L(G)$$\varepsilon$

$\leq n$$n \in \mathbb{N}$

$w = w_1 w' w_n \in L(G) \cap \Sigma^n$$n > 0$$w_1 \in \Sigma$$w_1 = a$$S \to aSa$$w_1 = b$$S \to bSb$$w'$$w$

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.

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)