Propiedades de lenguajes regulares

Sean $L_1$ y $L_2$ dos lenguajes regulares.

Unión:
$L=L_1\cup L_2$ es regular, porque podemos construir una expresión regular para $L$, teniendo las expresiones regulares para $L_1$ y $L_2$, más preciso: con $L_1=L(\alpha)$ y $L_2=L(\beta)$ tenemos $L=L((\alpha+\beta))$
Concatención:
$L=L_1.L_2$ es regular, porque podemos construir una expresión regular para $L$, teniendo las expresiones regulares para $L_1$ y $L_2$, más preciso: con $L_1=L(\alpha)$ y $L_2=L(\beta)$ tenemos $L=L(\alpha\beta)$
Clausura:
$L=L_1^*$ es regular, porque podemos construir una expresión regular para $L$, teniendo la expresión regular para $L_1$, más preciso: con $L_1=L(\alpha)$ tenemos $L=L((\alpha)^*)$
Complemento:
$L=\overline{L_1}=\mbox{$\Sigma^*$}-L_1$ es regular, porque podemos construir, dado un AFD completo $M_1$ que acepta $L_1$, un AFD $M$ que acepta $L$ simplemente `invertiendo' sus estados finales, es decir, los estados no finales de $M_1$ serán los estados finales de $M$ y los finales se convierten en los no finales, entonces, si $M_1=(\Sigma,Q,\delta,q_0,F)$ construimos $M=(\Sigma,Q,\delta,q_0,Q-F)$.
Intersección:
$L=L_1\cap L_2$ es regular, porque con las reglas de DeMorgan obtenemos $L=L_1\cup L_2=\overline{\overline{L_1}\cup\overline{L_2}}$. Complemento y unión producen lenguajes regulares, como visto antes. Dicha construcción es bastante laborosa, abajo vemos una construcción directa y simple.
Diferencia:
$L=L_1-L_2$ es regular, porque se puede expresar la diferencia como $L=L_1-L_2=L_1\cap \overline{L_2}=L_1\cap(\mbox{$\Sigma^*$}-L_2)$ y las operaciones usadas mantienen la regularidad.
En vez de usar la lógica booleana, es decir, aplicando las reglas de DeMorgan, se puede construir directamente un autómata que acepta el lenguaje $L=L_1\cap L_2$.
La idea principal es, simular en paralelo en un solo autómata (digamos autómata de producto) las transiciones de los dos autómatas (por ejemplo finitos deterministas y completas) para $L_1$ y $L_2$.
Entonces sean $M_1=(\Sigma_1,Q_1,\delta_1,q_1,F_1)$ y $M_2=(\Sigma_2,Q_2,\delta_2,q_2,F_2)$ los dos AFDs completos que aceptan $L_1$ y $L_2$, es decir, $L_1=L(M_1)$ y $L_2=L(M_2)$.
Construimos el AFD completo $M$ que acepta $L=L_1\cap L_2=L(M)$ como

\begin{displaymath}M=(\Sigma,Q,\delta,q_0,F) \end{displaymath}


donde
  • asumimos que $\Sigma=\Sigma_1=\Sigma_2$, es decir, usamos solamente los símbolos comunes. Es fácil eliminar en $M_1$ y en $M_2$ todas las dependencias de símbolos superflues antemano en caso que haya.
  • $Q=Q_1\times Q_2$, es decir, el producto cartesiano de los estados de $M_1$ y $M_2$.
  • $\delta$ es la función de transición con

    \begin{displaymath}\delta((p,q),\sigma)=(\delta_1(p,\sigma),\delta_2(q,\sigma)) \end{displaymath}


    para $p\in Q_1$, $q\in Q_2$ y $\sigma\in\Sigma$.
  • $q_0=(q_1,q_2)$, es decir, la pareja de los dos estados iniciales
  • $F=F_1\times F_2$, es decir, todas las parejas donde ambos estados son estados finales de ambos autómatas.

Comentarios

Publicar un comentario

Entradas más populares de este blog

Traductores: Ensambladores, compiladores e intérpretes

  Ensambladores:  son los encargados de transformar o traducir los programas escritos en ensamblador a su equivalente en código maquina o binario para que pueda ser ejecutado por la CPU. Este fue el primer lenguaje de programación que tradujo el lenguaje maquina a un lenguaje más natural para el ser humano. Con todo esto podemos decir que el lenguaje ensamblador es un lenguaje de programación de bajo nivel que se utiliza para escribir programas para computadoras, es la representación más directa del código máquina comprensible por los programadores. El lenguaje ensamblador se usó para la creación de programas en el pasado, actualmente se usa muy poco. Únicamente cuando se requiere un control directo del hardware o se quiere conseguir rendimientos poco comunes de los equipos. Un programa escrito con el lenguaje ensamblador seguirá los siguientes pasos: este programa tiene una serie de instrucciones que contienen las órdenes a seguir para llevar a cabo una acción. Todas...
Leer más

Clasificación de los Compiladores

El programa compilador traduce las instrucciones en un lenguaje de alto nivel a instrucciones que la computadora puede interpretar y ejecutar. Para cada lenguaje de programación se requiere un compilador separado. El compilador traduce todo el programa antes de ejecutarlo. Los compiladores son, pues, programas de traducción insertados en la memoria por el sistema operativo para convertir programas de cómputo en pulsaciones electrónicas ejecutables (lenguaje de máquina). Tipos compiladores: Una sola pasada:  examina el código fuente una vez, generando el código o programa objeto Pasadas múltiples:  requieren pasos intermedios para producir un código en otro lenguaje, y una pasada final para producir y optimizar el código producido durante los pasos anteriores. Optimación:  lee un código fuente, lo analiza y descubre errores potenciales sin ejecutar el programa. Compiladores incrementales:  generan un código objeto instrucción por instrucción (en vez de hacerlo ...
Leer más

Automatas de pila Unidad 2

Introducción De igual manera que los lenguajes regulares se pueden representar mediante autómatas finitos deterministas, los lenguajes independientes del contexto tienen su correspondencia en otro tipo de dispositivo: el Autómata a Pila (AP). Un autómata a pila es un dispositivo que tiene acceso a: Una secuencia de símbolos de entrada, que en general se representa por una cinta que se desplaza frente a un mecanismo de captación de dichos símbolos. El símbolo superior de una memoria en pila (LIFO) Un autómata a pila se encuentra en cada momento en un estado determinado y el estado siguiente depende de los tres elementos siguientes:  estado actual símbolo de entrada  símbolo superior de la pila Generalmente, el autómata a pila es no determinista en el sentido de que se permite que haya varias acciones posibles en cada momento. Un AP puede realizar dos tipos de operaciones elementales: Dependientes de la entrada.  Se lee la cinta y se av...
Leer más