Finite Automata (FA) és la màquina més senzilla per reconèixer patrons. S'utilitza per caracteritzar un llenguatge regular, per exemple: /baa+!/.
També s'utilitza per analitzar i reconèixer Expressions del llenguatge natural. L'autòmat finit o màquina d'estats finits és una màquina abstracta que té cinc elements o tuples. Té un conjunt d'estats i regles per passar d'un estat a un altre, però depèn del símbol d'entrada aplicat. Segons els estats i el conjunt de regles, la cadena d'entrada es pot acceptar o rebutjar. Bàsicament, és un model abstracte d'un ordinador digital que llegeix una cadena d'entrada i canvia el seu estat intern en funció del símbol d'entrada actual. Cada autòmat defineix un llenguatge, és a dir, un conjunt de cadenes que accepta. La figura següent mostra algunes característiques essencials de l'automatització general.

Figura: Característiques dels autòmats finits

La figura anterior mostra les següents característiques dels autòmats:

1. Entrada
2. Sortida
3. Estats dels autòmats
4. Relació d'estat
5. Relació de sortida

Un autòmat finit consta del següent:

javascript

Q : Finite set of states. ? : set of Input Symbols. q : Initial state. F : set of Final States. ? : Transition Function.>

L'especificació formal de la màquina és

{ Q, ?, q, F, ? }>

La FA es caracteritza en dos tipus:

1) Autòmats finits deterministes (DFA):

DFA consists of 5 tuples {Q, ?, q, F, ?}. Q : set of all states. ? : set of input symbols. ( Symbols which machine takes as input ) q : Initial state. ( Starting state of a machine ) F : set of final state. ? : Transition Function, defined as ? : Q X ? -->P.>

En un DFA, per a un caràcter d'entrada concret, la màquina només passa a un estat. Es defineix una funció de transició a cada estat per a cada símbol d'entrada. També a DFA no es permet el moviment nul (o?), és a dir, DFA no pot canviar d'estat sense cap caràcter d'entrada.

Per exemple, construïu un DFA que accepti un llenguatge de totes les cadenes que acabin amb 'a'.
Donat: ? = {a,b}, q = {q₀}, F={q₁}, Q = {q₀, q₁}

Primer, considereu un conjunt de llenguatges de totes les possibles cadenes acceptables per tal de construir un diagrama de transició d'estat precís.
L = {a, aa, aaa, aaaa, aaaaa, ba, bba, bbba, pare, pare, pare, pare}
A dalt hi ha un subconjunt simple de les possibles cadenes acceptables, hi pot haver moltes altres cadenes que acaben amb 'a' i conté símbols {a,b}.

Figura 1. Diagrama de transició d'estats per a DFA amb ? = {a, b}

Les cadenes no acceptades són,
ab, bb, aab, abbb, etc.

Taula de transició d'estat per a l'autòmat anterior,

Una cosa important a tenir en compte és, hi pot haver molts DFA possibles per a un patró . En general, es prefereix un DFA amb un nombre mínim d'estats.

2) Autòmats finits no deterministes (NFA): NFA és similar a DFA, excepte les funcions addicionals següents:

1. Es permet el moviment nul (o?), és a dir, es pot avançar sense llegir símbols.
2. Capacitat de transmetre a qualsevol nombre d'estats per a una entrada determinada.

Tanmateix, aquestes funcions anteriors no afegeixen cap poder a NFA. Si comparem tots dos en termes de potència, tots dos són equivalents.

A causa de les funcions addicionals anteriors, NFA té una funció de transició diferent, la resta és la mateixa que DFA.

?: Transition Function ?: Q X (? U ? ) -->2 ^ Q.>>> 
Com podeu veure a la funció de transició és per a qualsevol entrada inclosa nul (o?), NFA pot anar a qualsevol nombre d'estats. Per exemple, a continuació hi ha un NFA per al problema anterior.
  
Fig 2. Diagrama de transició d'estats per a NFA amb ? = {a, b}
 
Taula de transició d'estats per a l'autòmat anterior,
 
 
 
?EstatSímbol?
 
a
 
b
 
 
 
 
q0
 
{q0,q1}
 
q0
 
 
 
q1
 
?
 
?
 
 
 
 
Una cosa important a tenir en compte és,   a NFA, si algun camí per a una cadena d'entrada condueix a un estat final, llavors la cadena d'entrada     és     acceptat   . Per exemple, a l'NFA anterior, hi ha diversos camins per a la cadena d'entrada 00. Com que un dels camins condueix a un estat final, l'NFA anterior accepta 00.
 
  Alguns punts importants:  
string.format java
 
Justificació:
Com que totes les tuples a DFA i NFA són iguals excepte una de les tuples, que és la funció de transició (?)
  . No obstant això, hi ha una manera de convertir un NFA a DFA, per tant existeix un DFA equivalent per a cada NFA . 
 
 
Tant NFA com DFA tenen el mateix poder i cada NFA es pot traduir a DFA.
 
Hi pot haver diversos estats finals tant a DFA com a NFA.
 
NFA és més un concepte teòric.
 
DFA s'utilitza a l'anàlisi lèxica del compilador.
 
Si el nombre d'estats de la NFA és N, el seu DFA pot tenir un màxim de 2Nnombre d'estats.
 
 
Vegeu Quiz sobre expressió regular i autòmats finits.