- A minták felismerésére véges automatákat használnak.
- Bemenetként a szimbólum karakterláncát veszi, és ennek megfelelően megváltoztatja az állapotát. Amikor a kívánt szimbólum megtalálható, akkor megtörténik az átmenet.
- Az átmenet idején az automaták vagy a következő állapotba léphetnek, vagy ugyanabban az állapotban maradhatnak.
- A véges automatáknak két állapota van, Állapot elfogadása vagy Elutasított állapot . Ha a bemeneti karakterlánc feldolgozása sikeresen megtörtént, és az automata elérte a végső állapotát, akkor elfogadja.
Az FA formális meghatározása
A véges automata 5 sor (Q, ∑, δ, q0, F) gyűjteménye, ahol:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Véges automata modell:
A véges automatákat bemeneti szalaggal és véges vezérléssel lehet ábrázolni.
Bemeneti szalag: Ez egy lineáris szalag, amely bizonyos számú cellát tartalmaz. Minden bemeneti szimbólum minden cellába kerül.
Véges vezérlés: A véges vezérlés határozza meg a következő állapotot, amikor adott bemenetet fogad a bemeneti szalagról. A szalagolvasó balról jobbra egyesével olvassa be a cellákat, és egyszerre csak egy bemeneti szimbólumot olvas be.
Az automaták típusai:
Kétféle véges automata létezik:
- DFA (determinisztikus véges automata)
- NFA (nem determinisztikus véges automaták)
1. DFA
A DFA determinisztikus véges automatákra utal. A determinisztikus a számítás egyediségére utal. A DFA-ban a gép csak egy adott bemeneti karakterhez megy egy állapotba. A DFA nem fogadja el a nulláthelyezést.
2. NFA
Az NFA a nem-determinisztikus véges automaták rövidítése. Egy adott bemenethez tetszőleges számú állapot továbbítására szolgál. El tudja fogadni a null mozgást.
Néhány fontos pont a DFA-val és az NFA-val kapcsolatban:
- Minden DFA NFA, de az NFA nem DFA.
- Az NFA-ban és a DFA-ban is több végső állapot lehet.
- A DFA-t a Compiler Lexical Analysisben használják.
- Az NFA inkább elméleti fogalom.