Accettazione degli automi pushdown

Esistono due modi diversi per definire l'accettabilità del PDA.

Accettabilità dello Stato finale

Nell'accettabilità dello stato finale, un PDA accetta una stringa quando, dopo aver letto l'intera stringa, il PDA è in uno stato finale. Dallo stato iniziale, possiamo fare mosse che finiscono in uno stato finale con qualsiasi valore di stack. I valori dello stack sono irrilevanti fintanto che si finisce in uno stato finale.

Per un PDA (Q, ∑, S, δ, q 0 , I, F), il linguaggio accettato dall'insieme degli stati finali F è -

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

per qualsiasi stringa dello stack di input x.

Accettabilità dello stack vuoto

Qui un PDA accetta una stringa quando, dopo aver letto l'intera stringa, il PDA ha svuotato la sua pila.

Per un PDA (Q, ∑, S, δ, q 0 , I, F), la lingua accettata dallo stack vuoto è -

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

Esempio

Costruisci un PDA che accetti L = {0n 1n | n ≥ 0}

Soluzione

Questa lingua accetta L = {ε, 01, 0011, 000111, .............................}

Qui, in questo esempio, il numero di ‘a’ e ‘b’ deve essere lo stesso.

  • Inizialmente mettiamo un simbolo speciale ‘$’ nello stack vuoto.

  • Quindi allo stato q2, se incontriamo input 0 e top è Null, inseriamo 0 nello stack. Questo può iterare. E se incontriamo l'input 1 e top è 0, inseriamo questo 0.

  • Quindi allo stato q3, se incontriamo l'input 1 e top è 0, inseriamo questo 0. Anche questo può ripetersi. E se incontriamo l'input 1 e top è 0, inseriamo l'elemento top.

  • Se il simbolo speciale '$' viene incontrato in cima alla pila, viene estratto e alla fine passa allo stato di accettazione q 4 .

Esempio

Costruisci un PDA che accetti L = {ww R | w = (a + b) *}

Solution

Inizialmente mettiamo un simbolo speciale "$" nello stack vuoto. Allo statoq2, il wviene letto. Nello statoq3, ogni 0 o 1 viene visualizzato quando corrisponde all'input. Se viene fornito qualsiasi altro input, il PDA andrà in uno stato morto. Quando raggiungiamo quel simbolo speciale "$", andiamo nello stato di accettazioneq4.