En la sección anterior vimos que los lenguajes de dos gramáticas se pueden unir mediante la incorporación de un nuevo símbolo inicial y reglas de producción que vayan de ese nuevo símbolo a los símbolos iniciales de las gramáticas originales. La pregunta que surge inmediatamente es si podemos codificar algunas otras operaciones de lenguajes regulares.
Operaciones de lenguajes regulares como GLC #
Para lenguajes con las siguientes dos gramáticas
\(G_1=(V_1,\Sigma,P_1,S_1)\)
y
\(G_2=(V_2,\Sigma,P_2,S_2 )\)
se pueden definir las
siguientes gramáticas por operación de Lenguaje regular:
Unión #
La gramática que hace la unión de los dos lenguajes basado en sus gramáticas es: \[G_U=(V_1\cup V_2,\Sigma,P_1\cup P_2\cup \{S_U \rightarrow S_1 + S_2\},S_U )\]
Concatenación #
La gramática que hace la concatenación de los dos lenguajes basado en sus gramáticas es:
\[G_C=(V_1\cup V_2,\Sigma,P_1\cup P_2\cup \{S_C \rightarrow S_1 S_2\},S_C )\]Cerradura #
La gramática que hace la cerradura de un lenguaje basado en sus gramáticas es: \[G_*=(V_1,\Sigma,P_1\cup \{S_* \rightarrow S_1S_*|\epsilon \},S_* )\]
Los lenguajes regulares básicos como GLC #
Ya que es posible codificar las operaciones de lenguajes regulares a través de la creación de nuevas gramáticas (secuencia de operaciones) ¿Qué hay de los lenguajes básicos? Resulta que se pueden codificar como gramáticas
Lenguaje vació #
\[G=(V,\Sigma,\emptyset,S )\]Lenguaje de la cadena vacía #
\[G=(V,\Sigma,\{S \rightarrow \epsilon\},S )\]Lenguaje de un símbolo del alfabeto #
\[G=(V,\Sigma,\{S \rightarrow a\},S )\]Las GLC generan a cualquier LR #
El hecho de que se puedan definir los lenguajes básicos como gramáticas y que existan las operaciones para construir lenguajes más complejos con base a estos nos indica que una GLC puede generar un Lenguaje Regular!