PDA – Autômato com Pilha - Pushdown Automaton

Definição

• PDA = autômato finito com uma pilha adicional, que permite armazenar e recuperar informações de forma LIFO
  • LIFO = last-in, first-out
• essa memória extra permite reconhecer linguagens mais complexas que as regulares

Forma formal

• PDA = 7-tupla M = (Q,Σ,Γ,δ,q_0,Z_0,F), onde
  • Q = conjunto de estados
  • Σ - Sigma = alfabeto de entrada
  • Γ - Gamma = alfabeto da pilha
  • δ - delta = função de transição Q × (Σ ∪ {ε}) × Γ → P(Q × Γ∗)
  • q_0 ∈ Q = estado inicial
  • Z_0 ∈ Γ =símbolo inicial da pilha
  • F ⊆ Q = conjunto de estados finais

Funcionamento

• em cada passo, o PDA pode ler um símbolo de entrada, consultar o topo da pilha, e então
  • mudar de estado,
  • empilhar novos símbolos ou desempilhar,
  • ou ambos

Importância

• PDAs reconhecem linguagens livres do contexto, como
  • {a^n b^n | n ≥ 0
  • linguagens com estruturas de aninhamento
    • como parênteses balanceados

Observações

• um PDA não é tão poderoso quanto uma Máquina de Turing
• há PDAs determinísticos e não-determinísticos
  • nem toda GLC tem um PDA determinístico equivalente