A Função que comanda as leituras e gravações,

...

Uma computação nesta máquina de Turing pode ser, por exemplo: (a posição do cabeçote é indicada mostrando-se a célula em negrito)

Passo Estado Fita

----- ------ -------

1 s1 11

2 s2 ¬1

3 s2 ¬1¬

4 s3 ¬1¬¬

5 s4 ¬1¬1

6 s5 ¬1¬1

7 s5 ¬1¬1

8 s1 11¬1

9 s2 1¬¬1

10 s3 1¬¬1

11 s3 1¬¬1¬

12 s4 1¬¬11

13 s4 1¬¬11

14 s5 1¬¬11

15 s1 11¬11

- Autômato de Pilha

Autómato de pilha é um ε-NFA com uma pilha de símbolos. Adiciona a possibilidade de memorizar uma quantidade infinita de informação. Só tem acesso ao topo da pilha (LIFO), em vez de poder consultar qualquer posição de memória, como os computadores genéricos.

Autômatos com pilha escolhem uma transição analisando o símbolo atual na cadeia de entrada, o estado atual e o topo da pilha. Máquinas de estados finitos convencionais apenas analisam o símbolo na cadeia de entrada e o estado atual. Autômatos com pilha adicionam a pilha como recurso auxiliar, deste modo, dado um símbolo da cadeia de entrada, o estado atual e um símbolo no topo da pilha, uma transição é selecionada.

Um autômato de pilha é formalmente definido por uma 6-tupla:

- M= (Q, Σ, Γ, Δ, q0, Z0, F)

- Q: conjunto finito de estados

- Σ: conjunto finito de símbolos de entrada

- Γ: alfabeto da pilha finito

- Δ: função de transição Δ(q, a, X) = {(p1,γ1), …} finito

- q0: estado inicial

- F: conjunto de estados de aceitação ou finais

Um grande exemplo de uso do autômato de pilha é nos compiladores, onde os usam para fazer o controle de paridade de alguns caracteres como os parênteses, chave, colchete e etc.

---------------------------------------------------------------

Exemplo:

Função de Inserção:

( 3*5 )

Entrada

Pilha

Ação

(

VAZIA

(

(

(

(

)

(

Remover

)

VAZIA

X

( 3*5 )[pic 48]

Programa lê o parêntese aberto e pela função de transição insere na pilha.

(3*5)[pic 49]

Programa lê o parêntese fechado e pela função de transição remove na pilha.

Ao final da leitura a pilha está vazia, isto significa que a sentença foi aceita pelo autômato.