Autòmat finit determinista

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:^[1]

• ${\displaystyle Q\,}$ és un conjunt d'estats;
• ${\displaystyle \Sigma \,}$ és un alfabet;
• ${\displaystyle Q_{0}\in Q}$ és l'estat inicial;
• ${\displaystyle \Delta \colon Q\times \Sigma \to Q}$ és una funció de transició;
• ${\displaystyle 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.

Referències