Neste capítulo estudaremos uma máquina (um procedimento aceitador, ou reconhecedor), chamada autômato finito (af). A palavra finito é incluída no nome para ressaltar que um af só pode conter uma quantidade finita e limitada de informação, a qualquer momento. Essa informação é representada por um estado da máquina, e só existe um número finito de estados. Essa restrição faz com que o af seja severamente limitado na classe de linguagens que pode reconhecer, composta apenas pelas linguagens regulares, como mostraremos neste capítulo. Duas versões do af são estudadas aqui: o af determinístico (afd) e o af não determinístico (afnd).