Finite Automata (FA) je nejjednodušší stroj pro rozpoznávání vzorů. Používá se k charakterizaci regulárního jazyka, například: /baa+!/.
Také se používá k analýze a rozpoznávání výrazů přirozeného jazyka. Konečný automat nebo konečný automat je abstraktní stroj, který má pět prvků nebo n-tic. Má sadu stavů a ​​pravidel pro přechod z jednoho stavu do druhého, ale záleží na použitém vstupním symbolu. Na základě stavů a ​​sady pravidel může být vstupní řetězec buď přijat nebo odmítnut. V podstatě se jedná o abstraktní model digitálního počítače, který čte vstupní řetězec a mění jeho vnitřní stav v závislosti na aktuálním vstupním symbolu. Každý automat definuje jazyk, tj. sadu řetězců, které přijímá. Následující obrázek ukazuje některé základní rysy obecné automatizace.

Postava: Vlastnosti konečných automatů

Výše uvedený obrázek ukazuje následující vlastnosti automatů:

1. Vstup
2. Výstup
3. Stavy automatů
4. Státní vztah
5. Výstupní vztah

Konečný automat se skládá z následujících částí:

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

Formální specifikace stroje je

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

FA se dělí na dva typy:

1) Deterministické konečné automaty (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 ? -->Q.>

V DFA pro konkrétní vstupní znak přejde stroj pouze do jednoho stavu. Přechodová funkce je definována v každém stavu pro každý vstupní symbol. Ve službě DFA také není povolen přesun nuly (nebo ?), tj. DFA nemůže změnit stav bez jakéhokoli vstupního znaku.

Vytvořte například DFA, která přijímá jazyk všech řetězců končících na „a“.
Dané: ? = {a,b}, q = {q₀}, F={q₁}, Q = {q₀, q₁}

Nejprve zvažte jazykovou sadu všech možných přijatelných řetězců, abyste sestavili přesný diagram přechodu stavu.
L = {a, aa, aaa, aaaa, aaaaa, ba, bba, bbba, otec, otec, otec, otec}
Výše je jednoduchá podmnožina možných přijatelných řetězců, existuje mnoho dalších řetězců, které končí na „a“ a obsahují symboly {a,b}.

Obr 1. Diagram přechodu stavu pro DFA s ? = {a, b}

Neakceptované řetězce jsou,
ab, bb, aab, abbb atd.

Tabulka přechodu stavu pro výše uvedený automat,

Jedna důležitá věc, kterou je třeba poznamenat, pro vzor může být mnoho možných DFA . Obecně je preferována DFA s minimálním počtem stavů.

2) Nedeterministické konečné automaty (NFA): NFA je podobná službě DFA kromě následujících dalších funkcí:

1. Je povolen nulový (nebo ?) pohyb, tj. může se pohybovat vpřed bez čtení symbolů.
2. Schopnost vysílat do libovolného počtu stavů pro konkrétní vstup.

Tyto výše uvedené funkce však NFA nepřidávají žádnou sílu. Pokud porovnáme oba z hlediska výkonu, oba jsou ekvivalentní.

Kvůli výše uvedeným doplňkovým funkcím má NFA jinou přechodovou funkci, zbytek je stejný jako DFA.

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

Jak můžete vidět na přechodové funkci pro jakýkoli vstup včetně null (nebo ?), NFA může přejít do libovolného počtu stavů. Například níže je NFA pro výše uvedený problém.

Obr 2. Stavový diagram přechodu pro NFA s ? = {a, b}

Tabulka přechodu stavu pro výše uvedený automat,

Jedna důležitá věc, kterou je třeba poznamenat, v NFA, pokud nějaká cesta pro vstupní řetězec vede do konečného stavu, pak vstupní řetězec je přijato . Například ve výše uvedeném NFA existuje více cest pro vstupní řetězec 00. Protože jedna z cest vede do konečného stavu, výše uvedený NFA akceptuje 00.

Některé důležité body:

typy sítí

Odůvodnění:

In case of DFA ? : Q X ? -->Q V případě NFA? : Q X? --> 2Q>

Nyní, když budete pozorovat, zjistíte Q X? –> Q je součástí Q X ? –> 2^Q.

Na straně RHS je Q podmnožinou 2^Qcož znamená, že Q je obsaženo v 2^Qnebo Q je součástí 2^Qopak však není pravdou. Matematicky to tedy můžeme uzavřít každá DFA je NFA, ale ne naopak . Přesto existuje způsob, jak převést NFA na DFA, takže existuje ekvivalentní DFA pro každý NFA .

1. NFA i DFA mají stejnou sílu a každý NFA může být přeložen do DFA.
2. V DFA i NFA může existovat více konečných stavů.
3. NFA je spíše teoretický koncept.
4. DFA se používá v Lexikální analýze v kompilátoru.
5. Pokud je počet států v NFA N, pak může mít jeho DFA maximálně 2^Npočet států.

Viz Kvíz o regulárních výrazech a konečných automatech.