Determinación de ambigüedad en gramáticas libres de contexto

Question

¿Cuáles son algunas de las formas más comunes para determinar si una gramática es ambigua o no? ¿Cuáles son algunos de los atributos comunes que las gramáticas ambiguas?

Por ejemplo, considere la siguiente Gramática G:

$S \rightarrow S(E)|E$

$E \rightarrow (S)E|0|1|\epsilon$

Mi conjetura es que esta gramática no es ambiguo, porque de los paréntesis, no podría hacer un equivalente cadenas con distintas analizar los árboles. Fácilmente podría haber cometido un error ya que soy nuevo en esto. ¿Cuáles son algunos de los comunes enumeración de técnicas para intentar construir la misma cadena con diferentes analizar los árboles?

1. ¿Cómo puedo saber que estoy en lo correcto o equivocado?
2. ¿Cuáles son los atributos comunes de gramáticas ambiguas?
3. ¿Cómo podría demostrar esto a mí mismo de forma intuitiva?
4. ¿Cómo podría demostrar esto con formal de la matemática?

Answer 1

Para determinar si un contexto libre de la gramática es ambigua es indecidible (no existe ningún algoritmo que diga correctamente "sí" o "no" en un tiempo finito para todas las gramáticas). Esto no significa que no hay clases de gramáticas cuando una respuesta es posible.

Para probar una gramática ambigua, usted puede hacer como usted esquema: Encontrar una cadena con dos analiza. Para demostrar que es inequívoco es más difícil: tienes Que probar el de arriba no es posible. Se sabe que el $LL(k)$ $LR(k)$ gramáticas son ambiguos, y para $k = 1$ las condiciones son relativamente fáciles de comprobar.

Answer 2

que $G= (V,T,P,S)$, donde $P$ son:

• $S\to S(E)|E$
• $E\to (S)E|0|1|ϵ$

Ahora consideremos una cadena $w \in L(G)$

$w = (0)(0)()1$

Derivación izquierda construcción

$S\to E\to (S)E\to (0)E\to (0)(S)E\to (0)(0)E\to (0)(0)(S)E\to (0)(0)(ϵ)E\to (0)(0)()E\to (0)(0)()1.$

Construir la derivación correcta $S\to E\to (S)E\to (S)(S)E\to (S)(S)(S)E\to (S)(S)(S)1\to (S)(S)(ϵ)1\to (S)(S)()1\to (S)(0)()1\to (0)(0)()1.$

Hemos sido capaces de construir derivaciones distintas 2. Por lo tanto, esta gramática es ambigua.

"Si una gramática produce al menos 2 Análisis distinto árbol o derivaciones, luego la gramática es ambigua".