Un autómata finito (FA) es una máquina idealizada simple que se utiliza para reconocer patrones dentro de la entrada tomada de algún conjunto de caracteres (o alfabeto) C. El trabajo de un FA es aceptar o rechazar una entrada dependiendo de si el patrón definido por el FA ocurre en la entrada. Un autómata finito consta de: un conjunto finito S de N estados.