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
dado, consideremos una gráfica de tres estados
q0,q1,q2 con las transiciones:
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:
,
;
y como conjunto de estados finales consideremos a la unión
.
Esta nueva gráfica reconoce efectivamente a la suma A+B.
2. Para reconocer
``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:
,
,
y como conjunto de estados finales consideremos a FB.
Esta nueva gráfica reconoce efectivamente al producto .
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*.