Unión e Intersección de Lenguas Regulares con CFL – Part 1

Requisito previo: jerarquía de Chomsky , lenguajes regulares

Como todos sabemos, los lenguajes aceptados por autómatas finitos se denominan lenguajes regulares y los que son aceptados por autómatas pushdown se denominan lenguajes libres de contexto. Pero, cuando se trata de la unión o intersección de estos dos lenguajes, a algunas personas les resulta difícil de analizar. si la intersección resulta en un lenguaje regular o libre de contexto.

Lo primero que hay que observar es que todos los lenguajes regulares en realidad no tienen contexto, la razón es bastante simple. Una forma de llamar regular a un lenguaje es mediante el diseño de sus autómatas finitos equivalentes o, en otras palabras, si podemos diseñar un autómata finito para un lenguaje en particular, entonces solo podemos llamar a ese lenguaje: regular y lo mismo existe para los lenguajes libres de contexto, si es posible. para diseñar un autómata pushdown para un idioma en particular, entonces solo se llama contexto libre.

Ahora, un autómata push down en palabras simples es en realidad un autómata finito con una memoria provista como una pila infinita . Lo que debe observar es que es posible diseñar un autómata finito para un lenguaje en particular, luego también es posible diseñar su equivalente push down autómata, lo que tenemos que hacer es simplemente no usar la pila infinita disponible en él. Es así de simple. Observe esto y, finalmente, lo que obtendrá es que para cada lenguaje regular es posible diseñar autómatas finitos y, por lo tanto, empujar hacia abajo los autómatas. Esta es la razón por la que todos los lenguajes regulares también pueden denominarse libres de contexto o, en otras palabras, los idiomas regulares son un subconjunto de idiomas libres de contexto.

Unión de lenguaje regular con lenguaje libre de contexto:
como todos los lenguajes regulares son libres de contexto, la unión de ambos da como resultado un lenguaje libre de contexto. Pero siempre es bueno entender con la ayuda de un ejemplo.
Tomemos un lenguaje L1 = {0*1*} (regular) y L2 = {0^n1^n |n>=0} (sin contexto)
y dejemos que L=L1 U L2 resulte en la unión de ambos idiomas y eso será:

L = {0*1*} que es un lenguaje normal, pero dado que todos los idiomas normales no tienen contexto. Entonces, podemos decir que la unión de dos siempre da como resultado un lenguaje libre de contexto.

Intersección del lenguaje regular con el lenguaje libre de contexto:
debido a que ahora sabemos que todos los lenguajes regulares son un subconjunto de lenguaje libre de contexto, no hay problema para comprender la unión de dos, pero cuando hablamos de intersección nuevamente, la respuesta es el lenguaje libre de contexto. Sí, la intersección de un lenguaje regular y uno libre de contexto siempre da como resultado un lenguaje libre de contexto.

Tomemos nuevamente el ejemplo anterior en el que L1 y L2 son iguales, pero ahora dejemos que
L= L1 ∩ L2, lo que resultará fácilmente en
L={0^n1^n | n>=0} que no tiene contexto.
Puede tomar más ejemplos de este tipo y verificar que la unión y la intersección de un lenguaje regular y un lenguaje sin contexto siempre da como resultado un lenguaje sin contexto.

Leer el siguiente artículo: propiedades de cierre de los lenguajes libres de contexto

Este artículo es una contribución de Dimpy Varshni . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.