- Els autòmats finits s'utilitzen per reconèixer patrons.
- Pren la cadena de símbol com a entrada i canvia el seu estat en conseqüència. Quan es troba el símbol desitjat, es produeix la transició.
- En el moment de la transició, els autòmats poden passar al següent estat o romandre en el mateix estat.
- Els autòmats finits tenen dos estats, Acceptar l'estat o Rebutja l'estat . Quan la cadena d'entrada es processi correctament i l'autòmat hagi arribat al seu estat final, acceptarà.
Definició formal de FA
Un autòmat finit és una col·lecció de 5 tuples (Q, ∑, δ, q0, F), on:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Model d'autòmats finits:
Els autòmats finits es poden representar mitjançant cinta d'entrada i control finit.
Cinta d'entrada: És una cinta lineal que té un cert nombre de cèl·lules. Cada símbol d'entrada es col·loca a cada cel·la.
Control finit: El control finit decideix el següent estat en rebre una entrada particular de la cinta d'entrada. El lector de cintes llegeix les cel·les una per una d'esquerra a dreta, i alhora només es llegeix un símbol d'entrada.
Tipus d'autòmats:
Hi ha dos tipus d'autòmats finits:
- DFA (autòmats finits deterministes)
- NFA (autòmats finits no deterministes)
1. DFA
DFA es refereix a autòmats finits deterministes. Determinista fa referència a la singularitat del càlcul. Al DFA, la màquina passa a un estat només per a un caràcter d'entrada concret. DFA no accepta el moviment nul.
2. NFA
NFA significa autòmats finits no deterministes. S'utilitza per transmetre qualsevol nombre d'estats per a una entrada determinada. Pot acceptar el moviment nul.
Alguns punts importants sobre DFA i NFA:
- Cada DFA és NFA, però NFA no és DFA.
- Hi pot haver diversos estats finals tant a NFA com a DFA.
- DFA s'utilitza a l'anàlisi lèxica del compilador.
- NFA és més un concepte teòric.