Autòmat finit determinista

De Viquipèdia
Dreceres ràpides: navegació, cerca
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[modifica | modifica el codi]

Formalment, es defineix com una 5 - tupla ( Q , Σ, q 0 , δ, F ) on:[1]

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 | modifica el codi]

Referències[modifica | modifica el codi]

  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 març 2003, p. 17.