Introduzione agli automi pushdown

Struttura di base del PDA

Un automa pushdown è un modo per implementare una grammatica priva di contesto nello stesso modo in cui progettiamo DFA per una grammatica regolare. Un DFA può ricordare una quantità finita di informazioni, ma un PDA può ricordare una quantità infinita di informazioni.

Fondamentalmente un automa pushdown è -

"Finite state machine" + "a stack"

Un automa a spinta ha tre componenti:

• un nastro di input,
• un'unità di controllo, e
• una pila di dimensioni infinite.

L'intestazione dello stack esegue la scansione del simbolo superiore dello stack.

Uno stack fa due operazioni:

• Push - viene aggiunto un nuovo simbolo in alto.

• Pop - il simbolo in alto viene letto e rimosso.

Un PDA può leggere o meno un simbolo di input, ma deve leggere la parte superiore dello stack in ogni transizione.

Un PDA può essere formalmente descritto come una tupla di 7 (Q, ∑, S, δ, q ₀ , I, F) -

• Q è il numero finito di stati

• ∑ è l'alfabeto di input

• S è simboli di stack

• δ è la funzione di transizione: Q × (∑ ∪ {ε}) × S × Q × S *

• q₀è lo stato iniziale (q ₀ ∈ Q)

• I è il simbolo iniziale della pila superiore (I ∈ S)

• F è un insieme di stati accettanti (F ∈ Q)

Il diagramma seguente mostra una transizione in un PDA da uno stato q ₁ allo stato q ₂ , etichettato come a, b → c -

Questo significa allo stato q₁, se incontriamo una stringa di input ‘a’ e il simbolo superiore della pila è ‘b’, poi facciamo scoppiare ‘b’, spingere ‘c’ in cima alla pila e passare allo stato q₂.

Terminologie relative a PDA

Descrizione istantanea

La descrizione istantanea (ID) di un PDA è rappresentata da una terzina (q, w, s) dove

• q è lo stato

• w è un input non consumato

• s è il contenuto dello stack

Notazione del tornello

La notazione "tornello" viene utilizzata per collegare coppie di ID che rappresentano una o più mosse di un PDA. Il processo di transizione è indicato dal simbolo del tornello "⊢".

Considera un PDA (Q, ∑, S, δ, q ₀ , I, F). Una transizione può essere rappresentata matematicamente dalla seguente notazione del tornello:

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

Ciò implica che durante l'assunzione di una transizione dallo stato p per dichiarare q, il simbolo di input ‘a’ viene consumato e la parte superiore della pila ‘T’ è sostituito da una nuova stringa ‘α’.

Note - Se vogliamo zero o più mosse di un PDA, dobbiamo usare il simbolo (⊢ *) per questo.