Definição:

Autômatos com pilha

 

  • AUTÔMATO FINITO
  • ESTRUTURA DA PILHA
    • PILHA
      • Memória auxiliar
      • Não possue limite máximo de tamanho
      • Independente da fita de entrada
    • FUNCIONAMENTO
      • Ultimo simbolo gravado é o primeiro a ser lido
      • Base: é fixa e define o seu inicio
      • Topo: é variável e define a posição do ultimo simbolo gravado
  • NÃO DETERMINISMO
  • QUALQUER LLC PODE SER RECONHECIDA POR UM AP*

Autômatos com pilha - Definição

Duas definições universalmente aceitas diferem no critério de parada do autômato:

  • ESTADOS FINAIS
    • Valor inicial da pilha é vazio
    • AP para aceitando ao atingir um estado final
  • PILHA VAZIA
    • A pilha contém, inicialmente, um símbolo inicial
    • Não existem estados finais
    • O AP para aceitando, quando a pilha estiver vazia
  • AS DUAS DEFINIÇÕES SÃO EQUIVALENTES

 

AUTÔMATO A PILHA

  • FITA
    • Análoga à do autômato finito
  • PILHA
    • Memória auxiliar
    • Usada para leitura e gravação
    • Não possui tamanho fixo
    • Valor inicial vazio
    • Dividida em células
    • Cada célula
      • Símbolo de um alfabeto
      • Pode ser igual ao alfabeto de entrada
    • Leitura ou gravação
      • Sempre no topo
    • Possui o tamanho variável
  • UNIDADE DE CONTROLE

    Reflete o estado corrente da máquina possui:

  • CABEÇA DE FITA
    • Unidade de leitura podendo testar se leu toda a entrada
    • Acessa uma célula da fita de cada vez movimentando-se somente para a direita
  • CABEÇA DE PILHA
    • Unidade de leitura e gravação
    • LEITURA
      • Move para baixo
      • Acessa um símbolo de cada vez (topo) e exclui o símbolo lido
      • Testa se a pilha está vazia
    • GRAVAÇÂO
      • Move para cima
      • O símbolo gravado ficará sempre no topo da pilha
  • PROGRAMA OU FUNÇÃO DE TRANSIÇÃO
    • Programa
      • Comanda a leitura da fita
      • Comanda a leitura e gravação da pilha
      • Define o estado da máquina
    • Dependendo:
      • Estado corrente
      • Símbolo lido da fita e da pilha, determina:
        • Novo estado
        • Palavra a ser gravada
        • Se a cadeia é aceita ou não

Representação do autômato - Formalismo

Um autômato com pilha é representado por:

M=( Σ, Q ,δ ,q0 ,F ,V )

Σ – alfabeto de entrada

Q – conjunto de estados do autômato

δ – função de transição

q0 – Estado inicial do autômato

F – Estados finais do autômato

V – Alfabeto da pilha

Processamento de um AP

  • Sucessiva aplicação da função programa até ocorrer uma condição de parada
  • É possível que um AP nunca atinja uma condição de parada (Ciclo ou loop infinito, característica não-determinística)

Parada de um AP

  • Para aceitando ("cadeia")
    • Um dos caminhos assume um estado final
  • Para rejeitando ("cadeia")
    • Todos os caminhos alternativos rejeitam
  • Loop infinito
    • Pelo menos um caminho alternativo está em loop

 Autômatos a pilha e LLC*

  • A classe das linguagens reconhecidas pelos AP's é igual a classe dos LLC
  • Para qualquer GLC*, existe um AP que reconhece a linguagem gerada e sempre para contrução de um AP a partir de uma GLC

* AP - AUTÔMATO A PILHA

* LLC - LINGUAGEM LIVRE DE CONTEXTO

* GLC - GRÁMATICA LIVRE DE CONTEXTO