Propiedades de cierre de los lenguajes libres de contexto

Los lenguajes libres de contexto (CFL) son aceptados por autómatas pushdown . Los lenguajes libres de contexto pueden ser generados por gramáticas libres de contexto, que tienen producciones (reglas de sustitución) de la forma: 

A -> ρ (donde A ∈ N y ρ ∈ (T ∪ N)* y N es un no terminal y T es un terminal) 
  
Propiedades de la  
unión de lenguajes libres de contexto: Si L1 y L2 son dos lenguajes libres de contexto, su unión L1 ∪ L2 también estará libre de contexto. Por ejemplo, 
L1 = { un ^norte segundo ^norte c ^metro | metro >= 0 y norte >= 0 } y L2 = { un ^norte segundo ^metro C ^metro | norte >= 0 y metro >= 0 }  L3
= L1 ∪ L2 = { un norte segundo norte ^{C metro} ∪ ^un norte ^{segundo metro} C ^metro | n >= 0, m >= 0 } también es independiente del contexto. 
L1 dice que el número de a debe ser igual al número de b y L2 dice que el número de b debe ser igual al número de c. Su unión dice que cualquiera de las dos condiciones es verdadera. Por lo tanto, también es un lenguaje libre de contexto. 

Nota: Entonces, las CFL están cerradas bajo Union. 

  
Concatenación: si L1 y L2 son dos idiomas libres de contexto, su concatenación L1.L2 también será libre de contexto. Por ejemplo, 
L1 = { un ^norte segundo ^norte | norte >= 0 } y L2 = { do ^metro re ^metro | metro >= 0 }  ^L3 =
L1.L2 = { un norte segundo ^norte C ^metro re ^metro | m >= 0 and n >= 0} también está libre de contexto. 
L1 dice que el número de a debe ser igual al número de b y L2 dice que el número de c debe ser igual al número de d. Su concatenación dice que el primer número de a debe ser igual al número de b, luego el número de c debe ser igual al número de d. Por lo tanto, podemos crear un PDA que primero presionará para las a, aparecerá para las b, presionará para las c y luego aparecerá para las d. Por lo tanto, puede ser aceptado por autómatas pushdown, por lo tanto, sin contexto. 

Nota: Entonces, las CFL están cerradas bajo Concatenación. 

  
Cierre Kleene: si L1 es libre de contexto, su cierre Kleene L1* también será libre de contexto. Por ejemplo, 
L1 = { un ^norte segundo ^norte | norte >= 0 } 
L1* = { un ^norte segundo ^norte | n >= 0 }* también es independiente del contexto. 

Nota: Entonces, las CFL están cerradas bajo Kleen Closure. 

  
Intersección y complementación: si L1 y L2 son dos lenguajes libres de contexto, su intersección L1 ∩ L2 no necesita estar libre de contexto. Por ejemplo, 
L1 = { un ^norte segundo ^norte c ^metro | n >= 0 y m >= 0 } y L2 = (a ^m b ⁿ c ⁿ | n >= 0 and m >= 0 } 
L3 = L1 ∩ L2 = { a ⁿ b ⁿ c ⁿ | n >= 0 } no necesita estar libre de contexto. 
L1 dice que el número de a debe ser igual al número de b y L2 dice que el número de b debe ser igual al número de c. Su intersección dice que ambas condiciones deben ser verdaderas, pero los autómatas de empuje hacia abajo solo pueden comparar dos. Por lo tanto, no puede ser aceptado por autómatas pushdown, por lo tanto, no está libre de contexto. 
De manera similar, la complementación del lenguaje libre de contexto L1 que es ∑* – L1, no necesita estar libre de contexto. 

Nota: Por lo tanto, los CFL no están cerrados en Intersección y Complementación. 

  
Lenguajes 
deterministas libres de contexto Los CFL deterministas son un subconjunto de CFL que pueden ser reconocidos por PDA deterministas. El PDA determinista tiene solo un movimiento desde un estado dado y un símbolo de entrada, es decir, no tiene elección. Para que un idioma sea DCFL, debe quedar claro cuándo PUSh o POP. 

Por ejemplo, L1= { a ⁿ b ⁿ c ^m | m >= 0 and n >= 0} es un DCFL porque para a, podemos empujar en la pila y para b podemos abrir. Puede ser reconocido por PDA determinista. Por otro lado, L3 = { un norte ^{segundo norte} C metro ^∪ un norte ^{segundo metro} C ^metro | n >= 0, m >= 0 } no puede ser reconocido por DPDA porque el número de a y b puede ser igual o el número de b y c puede ser igual. Por lo tanto, solo puede ser implementado por NPDA. Por lo tanto, es CFL pero no DCFL. Nota: DCFL se cierra solo bajo complementación y homomorfismo inverso. Pregunta: Considere el idioma L1, L2, L3 como se indica a continuación. 

  

L1 = { un ^metro segundo ^norte | metro, norte >= 0 } 
L2 = { un ^norte segundo ^norte | norte >= 0 } 
L3 = { un ^norte segundo ^norte C ^norte | n >= 0 } 
¿Cuál de las siguientes afirmaciones NO ES VERDADERA? 
A. Push Down Automata (PDA) se puede usar para reconocer L1 y L2 
B. L1 es un lenguaje normal 
C. Los tres lenguajes son independientes del contexto 
D. La máquina de Turing se puede usar para reconocer los tres lenguajes 

Solución: la opción (A) dice que PDA se puede usar para reconocer L1 y L2. L1 contiene todas las strings con cualquier número. de un seguido de cualquier no. de B. Por lo tanto, puede ser aceptado por PDA. L2 contiene strings con n no. de a seguido de n no. de b. También puede ser aceptado por PDA. Entonces, la opción (A) es correcta. 
La opción (B) dice que L1 es regular. Es cierto que la expresión regular para L1 es a*b*. 
La opción (C) dice que L1, L2 y L3 son independientes del contexto. Los idiomas L3 contienen todas las strings con n no. de a seguido de n no. de b seguido de n no. de c Pero no puede ser aceptado por PDA. Entonces la opción (C) no es correcta. 
La opción (D) es correcta ya que la máquina de Turing se puede utilizar para reconocer los tres idiomas. 

  
Pregunta: El lenguaje L = { 0 ⁱ 12 ⁱ | i ≥ 0 } sobre el alfabeto {0, 1, 2} es: 
A. No recursivo 
B. Es recursivo y determinista CFL 
C. Es regular 
D. Es CFL pero no determinista CFL. 

Solución: el lenguaje anterior es CFL determinista en cuanto a 0, podemos empujar 0 en la pila y para 2 podemos sacar los 0 correspondientes. Como no hay ambigüedad que mueve a tomar, es determinista. Entonces, la opción correcta es (B). Como CFL es un subconjunto de recursivo, también es recursivo. 
  
Pregunta: Considere los siguientes idiomas: 
L1 = { 0 ⁿ 1 ⁿ | n≥0 } 
L2 = { wcwr | w ɛ {a,b}* } 
L3 = { wwr | w ɛ {a,b}* } 
¿Cuáles de estos lenguajes son lenguajes deterministas libres de contexto? 
A. Ninguno de los idiomas 
B. Solo L1 
C. Solo L1 y L2 
D. Los tres idiomas 

Solución: Languages ​​L1 contiene todas las strings en las que n 0 son seguidos por n 1. El PDA determinista se puede construir para aceptar L1. Para los 0, podemos subirlo a la pila y para los 1, podemos sacarlo de la pila. Por lo tanto, es DCFL. 
L2 contiene todas las strings de la forma wcwr donde w es una string de a y b y wr es el reverso de w. Por ejemplo, aabbcbbaa. Para aceptar este lenguaje, podemos construir un PDA que colocará todos los símbolos en la pila antes de c. Después de c, si el símbolo en la string de entrada coincide con el símbolo en la pila, se abre. Entonces, L2 también se puede aceptar con PDA determinista, por lo tanto, también es DCFL. 
L3 contiene todas las strings de la forma wwr donde w es una string de a y b y wr es el reverso de w. Pero no sabemos dónde termina wr y comienza wr. p.ej; aabbaa es una string correspondiente a L3. Para el primero a, lo empujaremos en la pila. Luego a puede ser parte de w o wr donde w=a. Por lo tanto, puede haber múltiples movimientos desde un estado en un símbolo de entrada. Por lo tanto, solo se puede usar PDA no determinista para aceptar este tipo de lenguaje. Por lo tanto, es NCFL no DCFL. 
Entonces, la opción correcta es (C). Solo, L1 y L2 son DCFL. 
  
Pregunta: ¿Cuál de las siguientes gramáticas genera el lenguaje L = { a ⁱ b ^j | i ≠ j } 
S -> CA | CB, C -> aCb | un | b, A -> aA | ɛ, B -> Bb | ɛ 
S -> aS | Sb | un | b 
S -> CA | CB, C -> aCb | ɛ, A -> aA | ɛ, B -> Sib | ɛ
S -> CA | CB, C -> aCb | ɛ, A -> aA | a, si -> sib | b 

Solución: La mejor manera de resolver este tipo de preguntas es eliminar las opciones que no cumplen las condiciones. Las condiciones para el lenguaje L es no. de a y no. de b debe ser desigual. 
En la opción (B), S => aS => ab. Puede generar strings con a y b iguales. Entonces, esta opción es incorrecta. 
En la opción (C), S => AC => C => ɛ. En ɛ, a y b son iguales (0), por lo que no es una opción correcta. 
En la opción (A), S se reemplazará por AC o CB. C generará no. de a es más que no. de b por 1 o no. de b es más que no. de a por 1. Pero un a más o un b más puede ser compensado por B -> bB | ɛ o A -> aA | ɛ respectivamente. Entonces puede dar strings con igual no. de a y b. Por lo tanto, no es una opción correcta. 
En la opción (D), S será reemplazado por AC o CB. C siempre generará igual no. de a y b. Si reemplazamos S por AC, A agrega al menos una a adicional. y si reemplazamos S por CB, B agregará al menos una b adicional. Entonces esta gramática nunca generará igual no. de a y b. Entonces, la opción (D) es correcta. 
  
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.