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.

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ó.

Definició formalModifica

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 2, sent q 1q 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éModifica

ReferènciesModifica

  1. Chakraborty, Samarjit «Formal Languages and Automata Theory. Regular Expressions and Finite Automata» (en anglès). Computer Engineering and Networks Laboratory. Swiss Federal Institute of Technology (ETH) Zürich, 17-03-2003, p. 17.