Una maquina de estados es una forma de implementar (muy grosso modo) un historico de lo que ha ido pasando en un programa o circuito. Por ejemplo, supongamos que quieres hacer un reconocedor lexico, y quieres interpretar la palabra "haber", tu maquina de estados comenzada en un estado incial, despues recibira como entrada de datos una "h" y como es lo que espera pasara a un estado2, si despues llega una "a", pasara a un estado3, pero si llega cualquier otra cosa, permanecera en el estado2.
La gracia de estas cosas esta en que puesto que estas en un estado2, tu sabes que para llegar ahi previamente has tenido que leer una "h", por lo que puedes reocontruir los datos que has leido hasta un estado determinado facilmente.
Los estados no son mas que flags (en el caso de ser biestables) booleanos, aunque se pueden hacer maquinas triestado y entonces el flag puede tener 3 valores que determinan 3 acciones diferentes.
Se pueden crear mediante programacion o mediantre circuiteria.
Si buscas un poco en google encontraras cantidades enormes de informacion sobre como hacer una.