Las Máquinas de estados o Autómatas, son  también denominadas máquinas teóricas o máquinas abstractas, éstas son  dispositivos teóricos capaces de recibir y transmitir información. Para poder realizar esta tarea, manipulan cadenas de símbolos que se le presentan como entrada, produciendo como salida otra tira o cadena de símbolos.
Para poder realizar esta tarea y determinar cuando corresponde producir un determinado símbolo de salida, lo realiza a través de un conjunto de estados finitos, en los cuales se puede encontrar la máquina  en un determinado intervalo de tiempo discreto, y este estado contendrá la información de la salida a producir dependiendo del símbolo de entrada

Como se mencionó en el párrafo anterior, la conducta de la máquina está gobernada por el “estado” en que se encuentre, y que ante una determinada entrada producida desde el exterior, la máquina podrá cambiar de estado y eventualmente producir una salida determinada. 

 Los orígenes de estos autómatas y el desarrollo posterior de las variantes tienen motivaciones diferentes, ya que se puede concluir que la Teoría de Autómatas proviene del campo de la Ingeniería Eléctrica, en donde principalmente los trabajos desarrollados por Shannon, demostraban la aplicación de la lógica matemática a los circuitos combinatorios y secuenciales. A posteriori, estos trabajos más los esfuerzos realizados por Church, Minsky, y otros , mas el postulado presentado por Alan Turing que dio origen a la máquina que lleva su nombre, culminaron con la formulación teórica de la Teoría de Autómatas. Se debe a Moore la presentación del primer tratado riguroso sobre autómatas, y recién en la década del 50 se comenzó a ver la utilidad de los autómatas con los lenguajes y las gramáticas.