Introdução ao Pushdown Automata

Estrutura Básica do PDA

Um autômato pushdown é uma maneira de implementar uma gramática livre de contexto de uma maneira semelhante à qual projetamos o DFA para uma gramática regular. Um DFA pode lembrar uma quantidade finita de informações, mas um PDA pode lembrar uma quantidade infinita de informações.

Basicamente, um autômato pushdown é -

"Finite state machine" + "a stack"

Um autômato pushdown tem três componentes -

  • uma fita de entrada,
  • uma unidade de controle, e
  • uma pilha com tamanho infinito.

O cabeçote da pilha verifica o símbolo do topo da pilha.

Uma pilha faz duas operações -

  • Push - um novo símbolo é adicionado no topo.

  • Pop - o símbolo superior é lido e removido.

Um PDA pode ou não ler um símbolo de entrada, mas tem que ler o topo da pilha em cada transição.

Um PDA pode ser formalmente descrito como um 7-tupla (Q, ∑, S, δ, q 0 , I, F) -

  • Q é o número finito de estados

  • ∑ é o alfabeto de entrada

  • S são símbolos de pilha

  • δ é a função de transição: Q × (∑ ∪ {ε}) × S × Q × S *

  • q0é o estado inicial (q 0 ∈ Q)

  • I é o símbolo inicial do topo da pilha (I ∈ S)

  • F é um conjunto de estados de aceitação (F ∈ Q)

O diagrama a seguir mostra uma transição em um PDA de um estado q 1 para o estado q 2 , rotulado como a, b → c -

Isso significa no estado q1, se encontrarmos uma string de entrada ‘a’ e o símbolo do topo da pilha é ‘b’, então nós estouramos ‘b’, empurrar ‘c’ no topo da pilha e mova para o estado q2.

Terminologias Relacionadas ao PDA

Descrição Instantânea

A descrição instantânea (ID) de um PDA é representada por um tripleto (q, w, s) onde

  • q é o estado

  • w é entrada não consumida

  • s é o conteúdo da pilha

Notação de torniquete

A notação "catraca" é usada para conectar pares de IDs que representam um ou vários movimentos de um PDA. O processo de transição é denotado pelo símbolo da catraca "⊢".

Considere um PDA (Q, ∑, S, δ, q 0 , I, F). Uma transição pode ser representada matematicamente pela seguinte notação de catraca -

(p, aw, Tβ) ⊢ (q, w, αb)

Isso implica que, embora haja uma transição do estado p declarar q, o símbolo de entrada ‘a’ é consumido, e o topo da pilha ‘T’ é substituído por uma nova string ‘α’.

Note - Se quisermos zero ou mais movimentos de um PDA, temos que usar o símbolo (⊢ *) para isso.