eliminacion de la ambiguedad

ELIMINACION DE LA AMBIGÜEDAD
Una GLC es ambigua si existe una cadena w Î L(G) que tiene más de una derivación por la izquierda o más de una derivación por la derecha o si tiene dos o más árboles dederivación. En caso de que toda cadena w Î  L(G) tenga un único árbol de derivación, la gramática no es ambigua.

Ejemplo: La gramática S ® aS| Sa | a es ambigua porque aa tiene dos derivacionespor la izquierda

  S Þ aS Þ aa  S Þ Sa Þ aa


Esta gramática genera el lenguaje a+ que también es el lenguaje generado por la gramática no ambigua S ® aS | a.

EJEMPLO
•La gramática paraexpresiones aritméticas sobre las variables x y y:
–E ®  E + E
–E ®  E * E
–E ®  x
–E ®  y
  es ambigua porque la cadena  x + y * x  tiene dos árboles de derivación:




TIPOS DE AMBIGÜEDADDentro del estudio de gramáticas existen dos tipos fundamentales de ambigüedad, los cuales son:

Ambigüedad Inherente: 
Las gramáticas que presentan este tipo de ambigüedad no pueden utilizarse paralenguajes de programación, ya que por más transformaciones que se realicen sobre ellas, nunca se podrá eliminar completamente la ambigüedad que presentan.
Un lenguaje L es inherentemente ambiguo sitodas sus gramáticas son ambiguas; si existe cuando menos una gramática no ambigua para L, L no es
ambiguo.
– El lenguaje de las expresiones no es Ambiguo
– Las expresiones regulares no son ambiguasEjemplo de un lenguaje inherentemente ambiguo:
L = {anbncmdm | n ³ 1, m ³ 1} È {anbmcmdn | n ³ 1, m ³ 1}

L es un LLC:
S ® AB | C
A ® aAb | ab C ® aCd | aDd
B ® cBd | cd D ® bDc | bc

Lagramática es ambigua: hay cadenas con más de una
derivación más izquierda:
 Considere: aabbccdd (m = n = 2)
 S ⇒ AB ⇒ aAbB ⇒ aabbB ⇒ aabbcBd ⇒ aabbccdd
 S ⇒ C ⇒ aCd ⇒ aaDdd ⇒ aabDcdd ⇒ aabbccdd- El lenguaje:
- L = {anbncmdm | n ³ 1, m ³ 1} È {anbmcmdn | n ³ 1, m ³ 1}
- La gramática
- S ® AB | C
A ® aAb | ab C ® aCd | aDd
B ® cCd | cd D ® bDc | bc
_ ¿Por qué todas las gramáticas...