- Finita automater används för att känna igen mönster.
- Den tar symbolsträngen som indata och ändrar dess tillstånd därefter. När den önskade symbolen hittas sker övergången.
- Vid tidpunkten för övergången kan automaten antingen flytta till nästa tillstånd eller stanna i samma tillstånd.
- Finita automater har två tillstånd, Acceptera tillstånd eller Avvisa tillstånd . När inmatningssträngen har bearbetats framgångsrikt och automaten nått sitt slutliga tillstånd, kommer den att acceptera.
Formell definition av FA
En finit automat är en samling av 5-tupel (Q, ∑, δ, q0, F), där:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Finita automatmodell:
Finita automater kan representeras av inmatningstejp och finita kontroll.
Inmatningsband: Det är ett linjärt band med ett visst antal celler. Varje inmatningssymbol placeras i varje cell.
Ändlig kontroll: Den ändliga kontrollen bestämmer nästa tillstånd vid mottagning av speciell inmatning från inmatningsbandet. Bandläsaren läser cellerna en efter en från vänster till höger, och åt gången läses endast en inmatningssymbol.
Typer av automater:
Det finns två typer av finita automater:
- DFA (deterministisk ändlig automat)
- NFA (icke-deterministiska finita automater)
1. DFA
DFA hänvisar till deterministiska finita automater. Deterministisk hänvisar till det unika i beräkningen. I DFA går maskinen till ett tillstånd endast för ett visst inmatningstecken. DFA accepterar inte nolldraget.
2. NFA
NFA står för icke-deterministiska finita automater. Den används för att överföra valfritt antal tillstånd för en viss ingång. Den kan acceptera noll-draget.
Några viktiga punkter om DFA och NFA:
- Varje DFA är NFA, men NFA är inte DFA.
- Det kan finnas flera sluttillstånd i både NFA och DFA.
- DFA används i Lexical Analysis i Compiler.
- NFA är mer ett teoretiskt begrepp.