next up previous contents
Siguiente: Estructura algebraica de las Un nivel arriba: Presentación formal Anterior: Interpretación estándar

De expresiones regulares a autómatas

Proposición 2.3   Todo lenguaje formalmente regular es regular.

En efecto, veamos que si L es un conjunto formalmente regular entonces existe una gráfica de transición que lo reconoce. Para esto, procederemos inductivamente según las construcciones de las expresiones regulares.


Casos básicos: 1. Cualquier gráfica de transición sin estados finales reconoce al conjunto vacío. 2. Para reconocer a la palabra vacía consideremos dos estados q0,q1. El primero, q0, es a la vez inicial y final. Bajo cualquier símbolo se pasa a q1 y ahí se queda cuando llega cualquier otro símbolo. Evidentemente, esta gráfica de transición s´ølo reconoce a la palabra vacía. 3. De manera similar, para un símbolo $s\in \Sigma$ dado, consideremos una gráfica de tres estados q0,q1,q2 con las transiciones:

\begin{displaymath}(q_0,t)\mapsto\left\{\begin{array}{ll}
q_1 &\mbox{\rm si $t=...
...ht.\ ;\ \mbox{\rm y para $i=1,2$ hagamos }\ (q_i,t)\mapsto q_2.\end{displaymath}

Al hacer inicial a q0, y final sólo a q1, se reconoce únicamente al símbolo s.


Casos inductivos: Supongamos construídas sendas gráficas de transición GA y GB que reconozcan a los lenguajes que interpretan a las expresiones regulares A y B. Sean q0A y q0B los respectivos estados iniciales y sean FA y FB los respectivos conjuntos de estados finales. 1. Para reconocer A+B introduzcamos un nuevo estado inicial q0 y la unión de ambas gráficas GA y GB. Tendamos transiciones vacías de q0 a cada uno de los estados iniciales q0A y q0B: $(q_0,\mbox{\it nil\/})\mapsto q_{0A}$, $(q_0,\mbox{\it nil\/})\mapsto q_{0B}$; y como conjunto de estados finales consideremos a la unión $F_{A}\cup F_{B}$. Esta nueva gráfica reconoce efectivamente a la suma A+B. 2. Para reconocer $A\cdot B$ ``pongamos a GA antes de GB'': Consideremos la unión de ambas gráficas GA y GB, como estado inicial tomamos a q0A, tendamos transiciones vacías de cada uno de los estados finales en FA al estado inicial q0B: $(q,\mbox{\it nil\/})\mapsto q_{0B}$, $q\in F_A$, y como conjunto de estados finales consideremos a FB. Esta nueva gráfica reconoce efectivamente al producto $A\cdot B$. 3. Para reconocer A* consideramos GA más un nuevo estado q0 que será el inicial de la nueva gráfica y su único estado final. Tendemos una transición vaciía de q0 al inicial anterior q0A y de cada estado final anterior tendemos una transición vacía a q0. Esta nueva gráfica reconoce efectivamente a la potencia estrella A*.


Veremos más adelante que el recíproco también es cierto: Todo lenguaje regular puede representarse mediante una expresión regular.
next up previous contents
Siguiente: Estructura algebraica de las Un nivel arriba: Presentación formal Anterior: Interpretación estándar
Guillermo Morales-Luna
2000-06-27