- DFA si riferisce ad automi finiti deterministici. Il determinismo si riferisce all'unicità del calcolo. Gli automi finiti sono detti automi finiti deterministici se alla macchina viene letta una stringa di input un simbolo alla volta.
- In DFA esiste un solo percorso per input specifici dallo stato corrente allo stato successivo.
- Il DFA non accetta la mossa nulla, ovvero il DFA non può cambiare stato senza alcun carattere di input.
- DFA può contenere più stati finali. Viene utilizzato nell'analisi lessicale nel compilatore.
Nel diagramma seguente, possiamo vedere che dallo stato q0 per l'input a c'è solo un percorso che va a q1. Allo stesso modo, da q0 esiste un solo percorso per l’input b che va a q2.
Definizione formale di DFA
Un DFA è una raccolta di 5 tuple come descritto nella definizione di FA.
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
La funzione di transizione può essere definita come:
lo scorrimento del mouse non funziona
δ: Q x ∑→Q
Rappresentazione grafica del DFA
Un DFA può essere rappresentato da digrafi chiamati diagrammi di stato. In quale:
- Lo stato è rappresentato dai vertici.
- L'arco etichettato con un carattere di input mostra le transizioni.
- Lo stato iniziale è contrassegnato da una freccia.
- Lo stato finale è indicato da un doppio cerchio.
Esempio 1:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} Soluzione:
Diagramma di transizione:
Tabella di transizione:
| Stato attuale | Stato successivo per l'ingresso 0 | Stato successivo dell'ingresso 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q2 | q1 |
| *q2 | q2 | q2 |
Esempio 2:
DFA con ∑ = {0, 1} accetta tutti quelli che iniziano con 0.
Soluzione:
Spiegazione:
- Nel diagramma sopra, possiamo vedere che, dato 0 come input per DFA nello stato q0, il DFA cambia stato in q1 e passa sempre allo stato finale q1 all'avvio dell'input 0. Può accettare 00, 01, 000, 001... .eccetera. Non può accettare alcuna stringa che inizia con 1, perché non passerà mai allo stato finale su una stringa che inizia con 1.
Esempio 3:
DFA con ∑ = {0, 1} accetta tutti quelli che terminano con 0.
Soluzione:
Spiegazione:
stringa n Java
Nel diagramma precedente, possiamo vedere che, dato 0 come input per il DFA nello stato q0, il DFA cambia stato in q1. Può accettare qualsiasi stringa che termina con 0 come 00, 10, 110, 100....ecc. Non può accettare alcuna stringa che termina con 1, perché non passerà mai allo stato finale q1 su 1 input, quindi la stringa che termina con 1 non verrà accettata o verrà rifiutata.