Please enable JavaScript.
Coggle requires JavaScript to display documents.
PDA - Coggle Diagram
PDA
La pila del PDA
Contiene i simboli che restano da espandere o confrontare
All'inizio si mette nella pila un simbolo speciale
$
Sopra di esso il simbolo iniziale della grammatica S
Da PDA a CFG
L'obiettivo è
costruire una grammatica
Che generi le stringhe accettate dal PDA
Prima della conversione, il PDA
Deve avere un
solo stato accettante
Deve svuotare completamente la pila prima di accettare
In ogni passaggio deve fare PUSH o POP
Deve avere un nuovo simbolo iniziale speciale
Può accettare solo se nella pila resta il simbolo speciale
Per costruire la CFG abbiamo variabili A_{pq}
p e q sono stati del PDA
Questo rappresenta
Tutte le stringhe che permettono di andare dallo stato p allo stato q
Partendo con la pila vuota e arrivando con la pila vuota
La variabile iniziale della nuova CFG
$$A_{q_0, q_{accept}}$$
Le 3 regole di produzione
Regola 1
--> Svuotamento finale
Si usa quando il PDA va da uno stato all'altro
Facendo prima push di un simbolo di pila
Per poi fare pop della stessa pila
$$A_{pq} \rightarrow aA_{rs}b$$
Regola 2
--> Svuotamento intermedio
Si usa quando il percorso da p a q
Può essere spezzato passando per uno stato r
In cui la pila si svuota completamente
$$A_{pq} \rightarrow A_{pr}A_{rq}$$
Regola 3
--> Regola base
Per andare da uno stato a se stesso
Senza fare alcun passo
Si produce la stringa vuota
$$A_{pp} \rightarrow \lambda$$
Il PDA lavora in modo ciclico
Caso 1
--> Se in cima alla pila c'è un NT A
Allora il PDA scegli una produzione A --> w
Esegue POP di A
Esegue PUSH della stringa w sulla pila
Caso 2
--> Se in cima alla c'è un terminale
Allora il PDA confronta il simbolo dell'input
Se coincidono
Legge il simbolo dall'input
Esegue POP dal terminale della pila
Il PDA continua finché la pila si riduce
Accetta quando rimane solo il simbolo $
E l'input è stato consumato correttamente