Automi a pila deterministici
Un’automa a pila deterministico (DPDA, dall’inglese Deterministic Push Down Automaton) è definito dalla tupla (Q, F, q0, I, Γ, δ), in cui:
- Q, F, q0, I, δ sono definiti esattamente come per i DFSA.
- Γ è l’alfabeto dei simboli di pila.
La funzione di transizione
Per un DPDA, la funzione di transizione è così definita:
δ: Q x I x Γ → Q x Γ*
Ovvero: considerato lo stato attuale, il simbolo di ingresso attuale, il simbolo attualmente in cima alla pila, la funzione di transizione indica qual è il nuovo stato da raggiungere e quali sono i nuovi simboli da scrivere in cima alla pila.
Se non si desidera scrivere alcun simbolo in cima alla pila, si utilizza la lettera ε.
La transizione
Ecco un esempio di transizione in un DPDA:
La transizione qui sopra indica che, se l’automa è nello stato A, in ingresso è letto il simbolo a e in cima alla pila si trova il simbolo Z0, allora bisogna passare allo stato B e:
- ri-scrivere sulla pila il simbolo Z0
- aggiungere, in cima alla pila, il simbolo A
Di fatto, questa transizione rimette al suo posto il simbolo Z0 appena letto, dopodiché mette sopra di esso, ovvero in cima alla pila, il simbolo A.
Il diagramma degli stati
Un’automa può essere efficacemente rappresentato attraverso un diagramma degli stati. Ecco un esempio di diagramma degli stati per un DPDA:
Lo stato iniziale è indicato attraverso una freccia che parte dal nulla e raggiunge tale stato.
Gli stati finali sono contraddistinti da una doppia circolettatura.
La tabella di transizione
Una funzione di transizione può essere efficacemente rappresentata attraverso una tabella di transizione.
Ecco un esempio di tabella di transizione, riferita all’automa dell’esempio precedente:
| Q\(I, Γ) | a, Z0 | a, A | b, Z0 | b, A | ε, Z0 | ε, A |
|---|---|---|---|---|---|---|
| q0 | q1, AZ0 | |||||
| q1 | q1, AA | q2, ε | ||||
| q2 | q2, ε | q3, Z0 | ||||
| q3 |
Tutte le celle vuote della tabella di transizione sarebbero delle transizioni verso uno stato pozzo, ovvero uno stato che conduce, senza dubbio, alla non accettazione della sequenza di ingresso.