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.