Automatas

La teoría de autómatas es una rama de las ciencias de la computacion que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría deautómatas está estrechamente relacionada con la teoría del lenguaje formal ya que los autómatas son clasificados a menudo por la clase de lenguajes formales que son capacesde reconocer. Un autómata es un modelo matemático para una maquina de estado finito (FSM sus siglas en inglés). Una FSM es una máquina que, dada una entrada de símbolos,"salta" a través de una serie de estados de acuerdo a una función de transición (que puede ser expresada como una tabla). En la variedad común "Mealy" de FSMs, esta funciónde transición dice al autómata a qué estado cambiar dados unos determinados estado y símbolo.
Autómata finito no determinista (AFND)
Los estados de un autómata de estetipo pueden, o no, tener una o más transiciones por cada símbolo del alfabeto. El autómata acepta una palabra si existe al menos un camino desde el estado q0 a un estado finalF etiquetado con la palabra de entrada. Si una transición no está definida, de manera que el autómata no puede saber como continuar leyendo la entrada, la palabra esrechazada.
Autómata finito no determinista con transiciones ε (AFND-ε)
Además de ser capaz de alcanzar más estados leyendo un símbolo, permite alcanzarlos sin leer ningúnsímbolo. Si un estado tiene transiciones etiquetadas con , entonces el AFND puede encontrarse en cualquier de los estados alcanzables por las transiciones , directamente o através de otros estados con transiciones . El conjunto de estados que pueden ser alcanzados mediante este método desde un estado q, se denomina la clausura  de q.