miniatura|Autòmat finit determinista que reconeix el llenguatge regular conformat exclusivament per les cadenes amb un nombre parell de zeros i un nombre parell d'uns. miniatura|Exemple d'AFD amb dos estats. En node de l'esquerra és inicial i d'acceptació. 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: é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.
Referències
Categoria:Llenguatges formals