- Eindige automaten worden gebruikt om patronen te herkennen.
- Het neemt de tekenreeks als invoer en verandert de status dienovereenkomstig. Wanneer het gewenste symbool wordt gevonden, vindt de overgang plaats.
- Op het moment van de overgang kunnen de automaten naar de volgende staat gaan of in dezelfde staat blijven.
- Eindige automaten hebben twee toestanden, Accepteer staat of Staat afwijzen . Wanneer de invoerreeks met succes is verwerkt en de automaat zijn eindstatus heeft bereikt, zal deze accepteren.
Formele definitie van FA
Een eindige automaat is een verzameling van 5 tupels (Q, ∑, δ, q0, F), waarbij:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Eindige Automaten-model:
Eindige automaten kunnen worden weergegeven door invoerband en eindige besturing.
Invoerband: Het is een lineaire tape met een bepaald aantal cellen. Elk invoersymbool wordt in elke cel geplaatst.
Eindige controle: De eindige controle bepaalt de volgende status bij het ontvangen van bepaalde invoer van invoerband. De bandlezer leest de cellen één voor één van links naar rechts, waarbij slechts één invoersymbool tegelijk wordt gelezen.
Soorten automaten:
Er zijn twee soorten eindige automaten:
- DFA(deterministische eindige automaten)
- NFA (niet-deterministische eindige automaten)
1. DFA
DFA verwijst naar deterministische eindige automaten. Deterministisch verwijst naar het unieke karakter van de berekening. In de DFA gaat de machine slechts naar één status voor een bepaald invoerteken. DFA accepteert de nulzet niet.
2. NFA
NFA staat voor niet-deterministische eindige automaten. Het wordt gebruikt om een willekeurig aantal toestanden voor een bepaalde invoer te verzenden. Het kan de nulzet accepteren.
Enkele belangrijke punten over DFA en NFA:
- Elke DFA is NFA, maar NFA is geen DFA.
- Er kunnen meerdere eindtoestanden zijn in zowel NFA als DFA.
- DFA wordt gebruikt bij lexicale analyse in Compiler.
- NFA is meer een theoretisch concept.