O Autômato de Pilha

Autômato de Pilha

        

1. O que é?        

• Autômato de pilha é um autômato que possui uma memória auxiliar.
• A memória auxiliar que esse autômato utiliza é um tipo abstrato de dados do tipo Pilha.

2. Características

• O autômato de pilha pode usar a informação que está no topo da pilha para decidir qual transição deve ser efetuada.
• Pode manipular a pilha ao efetuar uma transição.

3. Transições

As transações efetuadas por um autômato de pilha acontecem analisando:

• O símbolo atual na cadeia de entrada
• Estado atual
• Topo da pilha

Um autômato de pilha é semelhante a um autômato finito que reconhece as linguagens livres de contexto.

A principal característica é que o último símbolo a ser gravado é o primeiro a ser lido (LIFO).

4. Para que serve

Autômato de pilha é um autômato finito unificado com uma pilha na memória para realizar mecanismos mais sofisticados de reconhecimento de palavras.

A possibilidade de inserir e remover informações durante o processamento de uma cadeia, torna o autômato de pilha mais “poderoso” do que os Autômatos Finitos.

5. Como funciona

A pilha é iniciada com um valor inicial. Conforme for ocorrendo o processamento da cadeia, é verificado se o elemento está no topo da pilha. Caso o elemento do estado atual seja igual ao último elemento da pilha, esse elemento é adicionado à pilha. Caso contrário, o último elemento da pilha é removido. Quando chegar no final da leitura da cadeia e a pilha estiver vazia, a cadeia é aceita.

 

6. Formalismo

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

P = (Q, Σ, Γ, δ, q0, Z0, F) 

Onde:

• [pic 1] conjunto finito de estados.
• [pic 2] conjunto finito de símbolos de entrada (alfabeto).
• [pic 3]  alfabeto da pilha.
•  δ:Q × Σ × Γε → P(Q × Γε) relação de transição.
• [pic 4] estado inicial.
• [pic 5] conjunto de estados finais.
• Z0 símbolo de início da pilha (opcional)

Movimentação

Movimentação

A movimentação é determinada a partir de três informações:

1. Estado Corrente
2. Próximo símbolo
3. Símbolo armazenado no topo da fila

Possui a obrigatoriedade de consultar o símbolo presente no topo da pilha em qualquer transição.

Função é composta pela tripla δ(q, σ , γ):

        q é o Estado corrente;

        σ é o Símbolo lido;

        y é o Símbolo da pilha.

Cada elemento pode conter zero,um ou mais elementos, onde: 0 indica que não há movimentações possíveis, 1 é determinística e mais de 1 é não-determinística.