Please enable JavaScript.
Coggle requires JavaScript to display documents.
Automi a Pila (PDA) - Coggle Diagram
Automi a Pila (PDA)
E' un
automa finito non deterministico
Contiene una
memoria esterna
Pila / Stack
Serve per riconoscere
Linguaggi Context-Free
Un
automa finito
Possiede una
memoria molto limitata
Mentre il
PDA
Possiede una PIla
Che può ricordare molte più informazioni
Gestisce strutture e annidamenti
La
Pila
E' una
memoria esterna del PDA
Funziona con logica
LIFO
Le operazioni che possono essere fatte:
PUSH
--> Inserire un simbolo in cima alla pila
POP
--> togliere un simbolo che sta in cima alla pila
Equivalenza con le CFG
PDA e CFG sono equivalenti dal
punto di vista computazionale
Un linguaggio è CF
⇔
Esiste una CFG che lo genera
⇔
Esiste un PDA che lo riconosce
E' una
sestupla
Q
--> è l'insieme finito degli stati
∑
--> è l'alfabeto di input
Γ
--> è l'alfabeto della pila
$$\delta : Q \times \Sigma_\epsilon \times \Gamma_\epsilon \rightarrow P(Q \times \Gamma_\epsilon)$$
q_0
--> è lo stato iniziale
F
--> è l'insieme degli stati accettanti
Determinismo e non determinismo
Nei DFA e NFA hanno la stessa potenza
Nei PDA no
DPDA non è equivalente al PDA non deterministico
Quindi esistono linguaggi che possono essere riconosciuti solo da PDA non deterministici