2.6. Autómatas Finitos

Un reconocedor de un lenguaje es un programa que toma como entrada una cadena x y responde "sí" si x es una frase del programa, y "no", si no lo es. Se compila una expresión regular en un reconocedor construyendo un diagrama de transiciones generalizado llamado autómata finito. Un autómata finito puede ser determinista o no determinista, donde "no determinista" significa que en un estado se puede dar el caso de tener más de una transición para el mismo símbolo de entrada.

Tanto los autómatas finitos deterministas como los no deterministas pueden reconocer con precisión a los conjuntos regulares. Por tanto, ambos pueden reconocer con precisión lo que denotan las expresiones regulares. Sin embargo, hay un conflicto entre espacio y tiempo; mientras que un autómata finito determinista puede dar reconocedores más rápidos que uno no determinista, un autómata finito determinista puede ser mucho mayor que un autómata no determinista equivalente. En la siguiente sección, se introducen métodos para convertir expresiones regulares en ambas clases de autómatas finitos. La conversión en un autómata no determinista es más directa, por lo que primero se estudia este caso.