Teoria dos autômatos
De Wikipedia, a enciclopédia encyclopedia
Teoria dos autômatos é o estudo das máquinas abstratas ou autômatos, bem como problemas computacionais que podem ser resolvidos usando esses objetos. É objeto de estudo tanto da Ciência da Computação Teórica como da Matemática Discreta. A palavra autômato vem da palavra grega αὐτόματα que significa “autuação” (em tradução livre), isto é, sem influência externa.
A figura ao lado ilustra uma máquina de estados finito, que pertence a uma variedade bem conhecida de autômato. Este autômato consiste em estados (representados na figura por círculos), e transições (representadas por setas). Quando o autômato recebe um símbolo de entrada, ele faz uma transição (ou salto) para outro estado, de acordo com sua função de transição (que tem como entradas o estado atual e o símbolo recente). Teoria dos autômatos também está profundamente relacionada à teoria das linguagens formais. Um autômato é uma representação finita de uma linguagem formal que pode ser um conjunto infinito. Autômatos são frequentemente classificados pela classe das linguagens formais que são capazes de reconhecer, tipicamente ilustrado pela hierarquia de Chomsky, que descreve as relações entre várias línguas e tipos de lógica formalizada.
Autômatos desempenham um papel importante em teoria da computação, elaboração de compiladores, inteligência artificial, análise sintática e verificação formal.