Aceitação de autômatos de pushdown

Existem duas maneiras diferentes de definir a aceitabilidade do PDA.

Aceitabilidade do estado final

Na aceitabilidade do estado final, um PDA aceita uma string quando, depois de ler a string inteira, o PDA está em um estado final. Do estado inicial, podemos fazer movimentos que terminam em um estado final com quaisquer valores da pilha. Os valores da pilha são irrelevantes, desde que cheguemos a um estado final.

Para um PDA (Q, ∑, S, δ, q 0 , I, F), a linguagem aceita pelo conjunto de estados finais F é -

L (PDA) = {w | (q 0 , w, I) ⊢ * (q, ε, x), q ∈ F}

para qualquer string de pilha de entrada x.

Aceitabilidade de pilha vazia

Aqui, um PDA aceita uma string quando, depois de ler a string inteira, o PDA esvazia sua pilha.

Para um PDA (Q, ∑, S, δ, q 0 , I, F), a linguagem aceita pela pilha vazia é -

L (PDA) = {w | (q 0 , w, I) ⊢ * (q, ε, ε), q ∈ Q}

Exemplo

Construa um PDA que aceite L = {0n 1n | n ≥ 0}

Solução

Este idioma aceita L = {ε, 01, 0011, 000111, .............................}

Aqui, neste exemplo, o número de ‘a’ e ‘b’ tem que ser o mesmo.

  • Inicialmente, colocamos um símbolo especial ‘$’ na pilha vazia.

  • Então no estado q2, se encontrarmos a entrada 0 e o topo for Nulo, colocamos 0 na pilha. Isso pode iterar. E se encontrarmos a entrada 1 e o topo for 0, colocamos este 0.

  • Então no estado q3, se encontrarmos a entrada 1 e o topo for 0, estouramos este 0. Isso também pode iterar. E se encontrarmos a entrada 1 e o topo for 0, exibimos o elemento superior.

  • Se o símbolo especial '$' for encontrado no topo da pilha, ele é retirado e finalmente vai para o estado de aceitação q 4 .

Exemplo

Construa um PDA que aceite L = {ww R | w = (a + b) *}

Solution

Inicialmente, colocamos um símbolo especial '$' na pilha vazia. No estadoq2, a westá sendo lido. No estadoq3, cada 0 ou 1 é exibido quando corresponder à entrada. Se qualquer outra entrada for fornecida, o PDA irá para um estado morto. Quando alcançamos aquele símbolo especial '$', vamos para o estado de aceitaçãoq4.