- Automatele finite sunt folosite pentru a recunoaște tipare.
- Acesta ia șirul de simbol ca intrare și își schimbă starea în consecință. Când este găsit simbolul dorit, atunci are loc tranziția.
- În momentul tranziției, automatele pot fie să treacă la următoarea stare, fie să rămână în aceeași stare.
- Automatele finite au două stări, Acceptă starea sau Starea de respingere . Când șirul de intrare este procesat cu succes, iar automata a ajuns în starea sa finală, atunci va accepta.
Definiția formală a FA
Un automat finit este o colecție de 5 tuplu (Q, ∑, δ, q0, F), unde:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Model de automată finită:
Automatele finite pot fi reprezentate prin bandă de intrare și control finit.
Bandă de intrare: Este o bandă liniară care are un anumit număr de celule. Fiecare simbol de intrare este plasat în fiecare celulă.
Control finit: Controlul finit decide următoarea stare la primirea unei anumite intrări de la banda de intrare. Cititorul de bandă citește celulele una câte una de la stânga la dreapta și la un moment dat este citit doar un simbol de intrare.
Tipuri de automate:
Există două tipuri de automate finite:
- DFA (automate finite deterministe)
- NFA (automate finite nedeterministe)
1. DFA
DFA se referă la automate finite deterministe. Deterministul se referă la unicitatea calculului. În DFA, mașina trece la o stare numai pentru un anumit caracter de intrare. DFA nu acceptă mutarea nulă.
2. NFA
NFA înseamnă automate finite nedeterministe. Este folosit pentru a transmite orice număr de stări pentru o anumită intrare. Poate accepta mutarea nulă.
Câteva puncte importante despre DFA și NFA:
- Fiecare DFA este NFA, dar NFA nu este DFA.
- Pot exista mai multe stări finale atât în NFA, cât și în DFA.
- DFA este utilizat în analiza lexicală în compilator.
- NFA este mai mult un concept teoretic.