Expresión regular a autómata

 Conversión de una expresión regular a un autómata

En la parte (a) vemos cómo se maneja la expresión ε. Puede verse fácilmente que el lenguaje del autómata es {ε}, ya que el único camino desde el estado inicial a un estado de aceptación está etiquetado con ε

La parte (b) muestra la construcción de /0. Claramente, no existen caminos desde el estado inicial al de aceptación, por lo que /0 es el lenguaje de este autómata.

La parte (c) proporciona el autómata que reconoce una expresión regular a. Evidentemente, el lenguaje de este autómata consta de una cadena a, que es también L(a).

La expresión es de la forma R + S para dos expresiones R y S más pequeñas. Por tanto, el lenguaje del autómata de la (a) es L(R) ∪ L(S).

La expresión es de la forma RS para expresiones R y S más pequeñas. Por tanto, los caminos en el autómata de la (b) son todos y sólo los etiquetados con cadenas pertenecientes a L(R)L(S).

La expresión es de la forma R∗ para una expresión R más pequeña. Dicho camino acepta ε, que pertenece a L(R∗) sin importar qué expresión sea R.

Ejemplo