- DFA es refereix a autòmats finits deterministes. Determinista fa referència a la singularitat del càlcul. Els autòmats finits s'anomenen autòmats finits deterministes si la màquina es llegeix una cadena d'entrada un símbol a la vegada.
- A DFA, només hi ha un camí per a l'entrada específica des de l'estat actual fins al següent.
- DFA no accepta el moviment nul, és a dir, el DFA no pot canviar d'estat sense cap caràcter d'entrada.
- DFA pot contenir diversos estats finals. S'utilitza en l'anàlisi lèxica del compilador.
Al diagrama següent, podem veure que des de l'estat q0 per a l'entrada a, només hi ha un camí que va a q1. De la mateixa manera, a partir de q0, només hi ha un camí per a l'entrada b que va a q2.
Definició formal de DFA
Un DFA és una col·lecció de 5 tuples iguals que hem descrit a la definició de FA.
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
La funció de transició es pot definir com:
δ: Q x ∑→Q
Representació gràfica de DFA
Un DFA es pot representar mitjançant dígrafs anomenats diagrama d'estats. En quin:
- L'estat es representa amb vèrtexs.
- L'arc etiquetat amb un caràcter d'entrada mostra les transicions.
- L'estat inicial està marcat amb una fletxa.
- L'estat final es denota amb un cercle doble.
Exemple 1:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} Solució:
Diagrama de transició:
Taula de transició:
| Estat actual | Següent estat per a l'entrada 0 | Següent estat d'entrada 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q2 | q1 |
| *q2 | q2 | q2 |
Exemple 2:
DFA amb ∑ = {0, 1} accepta tots els que comencin per 0.
Solució:
Explicació:
- Al diagrama anterior, podem veure que a l'entrada donada 0 a DFA a l'estat q0, el DFA canvia d'estat a q1 i sempre passa a l'estat final q1 a l'entrada inicial 0. Pot acceptar 00, 01, 000, 001... .etc. No pot acceptar cap cadena que comenci per 1, perquè mai passarà a l'estat final en una cadena que comenci per 1.
Exemple 3:
DFA amb ∑ = {0, 1} accepta tots els que acaben en 0.
Solució:
Explicació:
Al diagrama anterior, podem veure que quan donat 0 com a entrada a DFA a l'estat q0, el DFA canvia d'estat a q1. Pot acceptar qualsevol cadena que acabi amb 0 com 00, 10, 110, 100... etc. No pot acceptar cap cadena que acabi amb 1, perquè mai passarà a l'estat final q1 en 1 entrada, de manera que la cadena que acabi amb 1 no s'acceptarà o serà rebutjada.