Teoria da Computação/Autômatos Finitos

Uma máquina de estados finitos (FSM - do inglês Finite State Machine) ou autômato finito é um modelo matemático usado para representar programas de computadores ou circuitos lógicos. O conceito é concebido como uma máquina abstrata que deve estar em um de seus finitos estados. A máquina está em apenas um estado por vez, este estado é chamado de estado atual. Um estado armazena informações sobre o passado, isto é, ele reflete as mudanças desde a entrada num estado, no início do sistema, até o momento presente. Uma transição indica uma mudança de estado e é descrita por uma condição que precisa ser realizada para que a transição ocorra. Uma ação é a descrição de uma atividade que deve ser realizada num determinado momento.

Máquinas de estado finito podem modelar um grande número de problemas, entre os quais a automação de design eletrônico, projeto de protocolo de comunicação, análise e outras aplicações de engenharia. Na biologia e na pesquisa da inteligência artificial, máquinas de estado ou hierarquias de máquinas de estado são, por vezes, utilizadas para descrever sistemas neurológicos e em linguística para descrever as gramáticas das linguagens naturais.