Ambigüedad en gramática libre de contexto y lenguajes libres de contexto – Part 1

Antes de leer este artículo, le recomendamos que primero lea sobre Pushdown Automata y Context Free Languages .
 
Supongamos que tenemos una gramática G libre de contexto con reglas de producción: S -> aSb | b Sa | SS | e
 
Derivación más a la izquierda (LMD) y árbol de derivación: La derivación más a la izquierda de una string a partir del símbolo inicial S se realiza reemplazando el símbolo no terminal más a la izquierda por RHS de la regla de producción correspondiente. Por ejemplo, la derivación más a la izquierda de la string abab de la gramática G anterior se realiza como:
S => a S b => ab S ab => abab
Los símbolos subrayados se reemplazan usando reglas de producción.
 
Árbol de derivación: indica cómo se deriva una string usando reglas de producción de S y se muestra en la Figura 1.

 
Derivación más a la derecha (RMD): la derivación más a la derecha de una string desde el símbolo inicial S se realiza reemplazando el símbolo no terminal más a la derecha por RHS de la regla de producción correspondiente. p.ej; La derivación más a la derecha de la string abab de la gramática G anterior se realiza como:
S => S S => Sa S b => S ab => a S bab => abab
Los símbolos subrayados se reemplazan usando reglas de producción. El árbol de derivación para abab usando la derivación más a la derecha se muestra en la Figura 2.

 
Una derivación puede ser LMD o RMD o ambas o ninguna. Por ejemplo, S => a S b => ab S ab => abab es LMD y RMD pero S => S S => Sa S b => S ab => a S bab => abab es RMD pero no LMD.
 
Gramática libre de contexto ambigua: una gramática libre de contexto se denomina ambigua si existe más de un LMD o más de un RMD para una string generada por la gramática. También habrá más de un árbol de derivación para una string en gramática ambigua. La gramática descrita anteriormente es ambigua porque hay dos árboles de derivación (Figura 1 y Figura 2). Puede haber más de un RMD para la string abab, que son:
S => S S => Sa S b => S ab => a S bab => abab
S => a S b => ab S ab => abab
 
Lenguajes libres de contexto ambiguo: Un lenguaje libre de contexto se llama ambiguo si hay no existe una gramática inequívoca para definir ese lenguaje y también se denomina lenguajes libres de contexto intrínsecamente ambiguos.
por ejemplo, L={a ⁿ b ⁿ c ^m } U {a ⁿ b ^m c ^m }
 
Nota:

• Si una gramática libre de contexto G es ambigua, el lenguaje generado por la gramática L(G) puede o no ser ambiguo.
• No siempre es posible convertir CFG ambiguo en CFG inequívoco. Solo algunos CFG ambiguos se pueden convertir en CFG no ambiguos.
• No existe un algoritmo para convertir CFG ambiguo en CFG inequívoco.
• Siempre existe un CFG inequívoco correspondiente a CFL inequívoco.
• Los CFL deterministas siempre son inequívocos y los analizan los analizadores LR.

 
Pregunta: Considere las siguientes afirmaciones sobre la gramática libre de contexto
G = {S -> SS, S -> ab, S -> ba, S -> ?}
I. G es ambigua
II. G produce todas las strings con el mismo número de a y b
III. G puede ser aceptado por un PDA determinista. ¿
 
Cuál de las siguientes combinaciones expresa todas las afirmaciones verdaderas sobre G?
A. Solo I
B. Solo I y III
C. Solo II y III
D. I, II y III
 
Solución: Hay diferentes LMD para la string abab que pueden ser
S => S S => S SS => ab S S = > abab S => abab
S => S S => ab S => abab
Así que la gramática es ambigua. Entonces la afirmación I es verdadera.
 
La declaración II establece que la gramática G produce todas las strings con el mismo número de a y b, pero no puede generar una string aabb. Entonces la declaración II es incorrecta.
La declaración III también es correcta ya que puede ser aceptada por PDA determinista. Entonces la opción correcta es (B).
 
Pregunta: ¿Cuál de las siguientes afirmaciones es FALSA?
R. Existen lenguajes libres de contexto tales que todas las gramáticas libres de contexto que los generan son ambiguas.
B. Una gramática libre de contexto inequívoca siempre tiene un árbol de análisis único para cada string del lenguaje generado por ella.
C. Tanto los autómatas pushdown deterministas como los no deterministas siempre aceptan el mismo conjunto de lenguajes.
D. Un conjunto finito de strings de un alfabeto es siempre un lenguaje regular.
 
Solución: (A) es correcta porque para CFL ambiguas, todas las CFG correspondientes son ambiguas.
(B) también es correcto, ya que CFG inequívoco tiene un árbol de análisis único para cada string del idioma generado por él.
(C) es falso ya que algunos lenguajes son aceptados por PDA no determinista pero no por PDA determinista.
(D) también es cierto ya que el conjunto finito de strings siempre es regular.
Entonces la opción (C) es la opción correcta.
 
La ambigüedad es una característica común de los lenguajes naturales, donde se tolera y se trata de diversas maneras. En los lenguajes de programación, donde solo debe haber una interpretación de cada declaración, la ambigüedad debe eliminarse cuando sea posible. A menudo podemos lograr esto reescribiendo la gramática en una forma equivalente y sin ambigüedades.
 
Este artículo ha sido aportado por Sonal Tuteja .
 
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.