Autòmat finit determinista
![](http://upload.wikimedia.org/wikipedia/commons/thumb/1/11/Automata_finito.png/220px-Automata_finito.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9d/DFAexample.svg/220px-DFAexample.svg.png)
Un autòmat finit determinista (abreujat AFD ) és un autòmat finit que a més és un sistema determinista, és a dir, per a cada estat en què es trobi l'autòmat, i amb qualsevol símbol de l'alfabet llegit, existeix sempre pel cap alt una transició possible des d'aquest estat i amb aquest símbol.
Definició formal
Formalment, es defineix com una 5 - tupla ( Q , Σ, q 0 , δ, F ) on:[1]
- és un conjunt d'estats;
- és un alfabet;
- és l'estat inicial;
- és una funció de transició;
- és un conjunt d'estats finals o d'acceptació.
En un AFD no poden donar-se cap d'aquests dos casos:
- Que hi hagi dues transicions del tipus δ (q, a)= q 1 i δ (q, a) =q ₂, sent q 1≠q 2 ;
- Que hi hagi transicions del tipus δ (q,ε), on ε és la cadena buida, llevat que q sigui un estat final, sense transicions cap a altres estats.
Vegeu també
- Autòmat finit
- Autòmat finit no determinista
- Trie, un exemple d'autòmat finit determinista.