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 q₀,q₁. El primero, q₀, es a la vez inicial y final. Bajo cualquier símbolo se pasa a q₁ 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 q₀,q₁,q₂ con las transiciones:

$$(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.$$

Al hacer inicial a q₀, y final sólo a q₁, se reconoce únicamente al símbolo s.


Casos inductivos: Supongamos construídas sendas gráficas de transición G_A y G_B que reconozcan a los lenguajes que interpretan a las expresiones regulares A y B. Sean q_0A y q_0B los respectivos estados iniciales y sean F_A y F_B los respectivos conjuntos de estados finales. 1. Para reconocer A+B introduzcamos un nuevo estado inicial q₀ y la unión de ambas gráficas G_A y G_B. Tendamos transiciones vacías de q₀ a cada uno de los estados iniciales q_0A y q_0B: $(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 G_A antes de G_B'': Consideremos la unión de ambas gráficas G_A y G_B, como estado inicial tomamos a q_0A, tendamos transiciones vacías de cada uno de los estados finales en F_A al estado inicial q_0B: $(q,\mbox{\it nil\/})\mapsto q_{0B}$, $q\in F_A$, y como conjunto de estados finales consideremos a F_B. Esta nueva gráfica reconoce efectivamente al producto $A\cdot B$. 3. Para reconocer A^* consideramos G_A más un nuevo estado q₀ que será el inicial de la nueva gráfica y su único estado final. Tendemos una transición vaciía de q₀ al inicial anterior q_0A y de cada estado final anterior tendemos una transición vacía a q₀. 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.
Siguiente: Estructura algebraica de las Un nivel arriba: Presentación formal Anterior: Interpretación estándar