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

Máquina de Turing

Imagen
Turing Alan Mathison Turing, OBE, fue un matemático, lógico, científico de la computación, criptógrafo, filósofo, biólogo teórico, maratoniano y corredor de ultradistancia británico. ​​​​​ Es considerado uno de los padres de la ciencia de la computación y precursor de la informática moderna. DISEÑAR UNA MAQUINA DE TURING QUE CALCULA EL NUMERO CONSECUTIVO DE UN NUMERO DADO EN BINARIO Si el número es par, su último bit es 0. La máquina sólo tiene que cambiar este 0 por un 1. Si el número es impar, su último bit es 1. En este caso, se tiene que cambiar por 0’s todos los 1’s seguidos que haya escritos de derecha a izquierda hasta llegar al primer 0, que se cambia por un 1. Si no hay ningún 0, entonces se tiene que añadir un 1 delante del número (añadir un bit). Es decir, escribir un 1 en la casilla en blanco (B) a la izquierda del número. Vamos a considerar tres estados: q0,q1,q2q0,q1,q2 ·              ...
Leer más

TEORIA DE LA COMPUTACION

La teoría de la computación es una rama de la matemática y la computación que centra su interés en las limitaciones y capacidades fundamentales de las computadoras. Específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un cómputo (cuenta o cálculo) y la clasificación de problemas. Teoría de autómatas Esta teoría provee modelos matemáticos que formalizan el concepto de computadora o algoritmo de manera suficientemente simplificada y general para que se puedan analizar sus capacidades y limitaciones. Algunos de estos modelos juegan un papel central en varias aplicaciones de las ciencias de la computación, incluyendo procesamiento de texto, compiladores, diseño de hardware e inteligencia artificial. Teoría de la computabilidad Esta teoría explora los límites de la posibilidad de solucionar problemas mediante algoritmos. Gran parte de las ciencias computacionales están dedicadas a resolver problemas de forma algorítmica, de manera que e...
Leer más

Gramáticas independientes del contexto Unidad 2

Conceptos generales  Chomsky: G3⊂G2⊂G1⊂G Definición ΣN - un conjunto de símbolos no terminales (variables) ΣT - un conjunto de símbolos terminales P - un conjunto de reglas de producción S∈ΣN un símbolo no terminal de ΣN La cuaterna (ΣT, ΣN , S, P) se llama gramática independiente del contexto (Gramáticas de tipo 2, según la clasificación de Chomsky) si todas las reglas de producción de P tienen la forma: A::= β, siendo A∈ΣN y β∈ Σ Todo lenguaje generado por una GIC G (se denota por L(G)) se llama Lenguaje independiente del contexto. Ejemplos: G1={{a,b},{S},S,{S::=aSb | ab}} G2={{a,b},{S},S,{S::=aSbb | abb}} G3={{a,b},{S},S,{S::=a | bS }} G4={{a,b},{S},S,{S::=aSb | SS | λ}} G5={{a,b},{S},S,{S::=aS | Sb | a | b}}  Motivación Representación de la sintaxis de lenguajes de programación; descripción de la estructura de lenguajes de marcado (DTD en XML, …); generadores de compiladores (Yacc, …), etc. Justificación Sea la ...
Leer más