Autómatos

Máquina de Turing

Permite (em teoria) implementar qualquer programa computável.

Assenta numa máquina de estados finita, numa "cabeça" de leitura/escrita de símbolos e numa fita infinita (onde se escreve ou lê esses símbolos).

A "cabeça" de leitura/escrita pode movimentar-se uma posição para esquerda ou direita.

Pouco relevante na implementação prática de processadores de linguagens.

A máquina de estados finita (FSM) tem acesso ao símbolo actual e decide a próxima acção a ser realizada.

A acção consiste na transição de estado e qual a operação sobre a fita.

Se não for possível nenhuma acção, a entrada é rejeitada.

Autómatos linearmente limitados

Diferem das MT pela finitude da fita.

Autómatos de pilha

"Cabeça" apenas de leitura e suporte de uma pilha sem limites.

Movimento da "cabeça" apenas numa direcção.

Autómatos adequados para análise sintáctica.

Autómatos finitos

Sem escrita de apoio à máquina de estados.

Autómatos adequados para análise léxica.