Finite Automata(FA) är den enklaste maskinen för att känna igen mönster. Den används för att karakterisera ett vanligt språk, till exempel: /baa+!/.
Det används också för att analysera och känna igen naturliga språkuttryck. Den finita automaten eller finita tillståndsmaskinen är en abstrakt maskin som har fem element eller tupler. Den har en uppsättning tillstånd och regler för att flytta från ett tillstånd till ett annat, men det beror på den använda inmatningssymbolen. Baserat på tillstånden och uppsättningen regler kan inmatningssträngen antingen accepteras eller avvisas. I grund och botten är det en abstrakt modell av en digital dator som läser en ingångssträng och ändrar dess interna tillstånd beroende på den aktuella ingångssymbolen. Varje automat definierar ett språk, dvs en uppsättning strängar som den accepterar. Följande figur visar några väsentliga funktioner för allmän automatisering.

Figur: Funktioner i Finite Automata

Bilden ovan visar följande funktioner hos automater:

försök fånga java

1. Inmatning
2. Produktion
3. Tillstånd av automater
4. Statsförhållande
5. Utgångsförhållande

En finit automat består av följande:

Q : Finite set of states. ? : set of Input Symbols. q : Initial state. F : set of Final States. ? : Transition Function.>

Formell specifikation av maskin är

{ Q, ?, q, F, ? }>

FA kännetecknas av två typer:

1) Deterministisk ändlig automat (DFA):

DFA consists of 5 tuples {Q, ?, q, F, ?}. Q : set of all states. ? : set of input symbols. ( Symbols which machine takes as input ) q : Initial state. ( Starting state of a machine ) F : set of final state. ? : Transition Function, defined as ? : Q X ? -->F.>

I en DFA, för ett visst indatatecken, går maskinen endast till ett tillstånd. En övergångsfunktion definieras för varje tillstånd för varje ingångssymbol. Också i DFA är null (eller ?) flytta inte tillåtet, dvs. DFA kan inte ändra tillstånd utan något inmatningstecken.

Till exempel, konstruera en DFA som accepterar ett språk av alla strängar som slutar med 'a'.
Givet: ? = {a,b}, q = {q₀}, F={q₁}, Q = {q₀, q₁}

Överväg först en språkuppsättning av alla möjliga acceptabla strängar för att konstruera ett korrekt tillståndsövergångsdiagram.
L = {a, aa, aaa, aaaa, aaaaa, ba, bba, bbba, far, far, far, far}
Ovan är en enkel delmängd av möjliga acceptabla strängar, det kan många andra strängar som slutar med 'a' och innehåller symboler {a,b}.

Fig 1. Tillståndsövergångsdiagram för DFA med ? = {a, b}

Strängar som inte accepteras är,
ab, bb, aab, abbb, etc.

Tillståndsövergångstabell för ovanstående automat,

En viktig sak att notera är, det kan finnas många möjliga DFA för ett mönster . En DFA med ett minsta antal tillstånd är i allmänhet att föredra.

2) Nondeterministic Finite Automata (NFA): NFA liknar DFA förutom följande ytterligare funktioner:

1. Noll (eller ?) rörelse är tillåten, dvs. den kan gå framåt utan att läsa symboler.
2. Möjlighet att sända till valfritt antal tillstånd för en viss ingång.

Dessa funktioner ovan ger dock ingen kraft till NFA. Om vi ​​jämför båda när det gäller kraft är båda likvärdiga.

På grund av ovanstående extrafunktioner har NFA en annan övergångsfunktion, resten är samma som DFA.

?: Transition Function ?: Q X (? U ? ) -->2 ^ F.>

Som du kan se i övergångsfunktionen är för alla indata inklusive noll (eller ?), kan NFA gå till valfritt antal stater. Till exempel nedan är en NFA för ovanstående problem.

Fig 2. Tillståndsövergångsdiagram för NFA med ? = {a, b}

Tillståndsövergångstabell för ovanstående automat,

En viktig sak att notera är, i NFA, om någon väg för en indatasträng leder till ett slutligt tillstånd, då inmatningssträngen är accepterad . Till exempel, i ovanstående NFA, finns det flera vägar för inmatningssträngen 00. Eftersom en av vägarna leder till ett slutligt tillstånd, accepteras 00 av ovanstående NFA.

Några viktiga punkter:

Berättigande:

In case of DFA ? : Q X ? -->F När det gäller NFA? : F X ? --> 2Q>

Om du nu observerar kommer du att få reda på Q X? –> Q är en del av Q X ? –> 2^Q.

På RHS-sidan är Q delmängden av 2^Qvilket indikerar att Q ingår i 2^Qeller Q är en del av 2^Qmen det omvända är inte sant. Så matematiskt kan vi dra slutsatsen att varje DFA är NFA men inte vice versa . Ändå finns det ett sätt att konvertera en NFA till DFA, så det finns en motsvarande DFA för varje NFA .

1. Både NFA och DFA har samma kraft och varje NFA kan översättas till en DFA.
2. Det kan finnas flera sluttillstånd i både DFA och NFA.
3. NFA är mer ett teoretiskt begrepp.
4. DFA används i Lexical Analysis i Compiler.
5. Om antalet stater i NFA är N kan dess DFA ha maximalt 2^Nantal stater.

Se frågesport om reguljära uttryck och finita automater.