Autòmat finit determinista

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.

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 ₀ , δ, F ) on:

• $Q\,$ és un conjunt d'estats;
• $\Sigma \,$ és un alfabet;
• $Q_{0}\in Q$ és l'estat inicial;
• $\Delta \colon Q\times \Sigma \to Q$ és una funció de transició;
• $F\subseteq Q$ é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 ₁ i δ (q, a) =q ₂, sent q ₁≠q ₂ ;
• 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.