¿Esta gramática de BNF es ambigua?

Question

Tengo un BNF definido de la siguiente manera:

<S> -> 0
<S> -> 1
<S> -> <S><S>

Creo que esta gramática no es ambigua, pero la solución fue "sí". ¿Alguna idea?
La solución del libro es impar para mí, porque creo que es la misma que la de arriba.

<S>-> 0|1|<S><S>

Gracias,
Chan

Answer 1

Una técnica general para comprobar la ambigüedad es ésta. Transformar la gramática en un sistema de ecuaciones:

$S(x) = S(x)^2 + 2x$

Resolver para $S(x)$ rinde $S(x) = \frac{1}{2}(1 - \sqrt{1 - 8x})$ que es la función generadora ordinaria que enumera los árboles de derivación izquierda de la gramática.

El lenguaje generado es $\{0,1\}^+$ que tiene la función generadora $\frac{1}{1-2x} - 1$ . Esto es obviamente diferente de lo anterior, por lo que hay más árboles de derivación a la izquierda (para palabras de longitud $n$ ) que las palabras (de longitud $n$ ).

Esta técnica se remonta a Chomsky y Schützenberger, 1963 ( PDF ).

Answer 2

Considere lo siguiente:

$S \to S S \to S S S \to 1 S S \to 1 1 S \to 1 1 1$

$S \to S S \to 1 S \to 1 S S \to 1 1 S\to 1 1 1$

Answer 3

Considera que la cadena = 000

1) S = S S = (S S) S = (0 0) 0 = 000

2) S = S S = S ( S S) = 0 (0 0 ) = 000

Answer 4

Usted puede escribir LHS (lado izquierdo) de su BNF y RHS (lado derecho) como cmt anterior para resolver eso. Después de tener LHS y RHS de su BNF, vamos a comparar dos de estos, si no hay diferencia entre estos => Su BNF no ambigua y viceversa. Buena suerte :D