Please enable JavaScript.
Coggle requires JavaScript to display documents.
PDA deterministico (DPDA) - Coggle Diagram
PDA deterministico (DPDA)
Significa
automa a pila deterministico
E' una versione del PDA
In cui in ogni situazione è possibile fare al massimo una mossa
Il
PDA non deterministico
Può avere più scelte possibili
Il DPDA non può avere più scelte contemporanee
DFA e NFA sono
equivalenti
Mentre DPDA e PDA non lo sono
Quindi esistono linguaggi CF che possono essere riconosciuti da un PDA ma non da un DPDA
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) \cup {{\emptyset}}$$
q_0
--> è lo stato iniziale
F
--> è l'insieme degli stati accettanti
Nei DPDA è consenti fare mosse a vuoto
Devono restare nel determinismo
Una parola viene accettata
Se dopo aver letto tutto l'input
L'automa si ferma in uno stato accettante
Il DPDA può rifiutare
Finisce in uno stato non accettante
Errore di pila vuota
Loop infinito