- Ierobežotie automāti tiek izmantoti, lai atpazītu modeļus.
- Tas izmanto simbola virkni kā ievadi un attiecīgi maina tā stāvokli. Kad vēlamais simbols ir atrasts, notiek pāreja.
- Pārejas brīdī automāti var pāriet uz nākamo stāvokli vai palikt tajā pašā stāvoklī.
- Galīgiem automātiem ir divi stāvokļi, Pieņemt stāvokli vai Noraidīšanas stāvoklis . Kad ievades virkne ir veiksmīgi apstrādāta un automāts sasniegs galīgo stāvokli, tas tiks pieņemts.
FA formāla definīcija
Galīgs automāts ir 5 korpusu kopums (Q, ∑, δ, q0, F), kur:
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Ierobežots automāta modelis:
Galīgos automātus var attēlot ar ievades lenti un ierobežotu vadību.
Ievades lente: Tā ir lineāra lente ar noteiktu šūnu skaitu. Katrs ievades simbols tiek ievietots katrā šūnā.
Ierobežota kontrole: Ierobežotā vadība nosaka nākamo stāvokli, saņemot noteiktu ievadi no ievades lentes. Lentes lasītājs nolasa šūnas pa vienai no kreisās puses uz labo, un vienlaikus tiek nolasīts tikai viens ievades simbols.
Automātu veidi:
Ir divu veidu galīgie automāti:
- DFA (deterministiski galīgi automāti)
- NFA (nedeterministiski galīgi automāti)
1. DFA
DFA attiecas uz deterministiskiem galīgiem automātiem. Deterministisks attiecas uz aprēķina unikalitāti. Izmantojot DFA, iekārta pāriet uz vienu stāvokli tikai noteiktai ievades rakstzīmei. DFA nepieņem nulles pārvietošanu.
2. NFA
NFA apzīmē nedeterministiskus galīgus automātus. To izmanto, lai pārsūtītu neierobežotu skaitu stāvokļu konkrētai ievadei. Tas var pieņemt nulles kustību.
Daži svarīgi punkti par DFA un NFA:
- Katrs DFA ir NFA, bet NFA nav DFA.
- Gan NFA, gan DFA var būt vairāki galīgie stāvokļi.
- DFA tiek izmantots kompilatora leksiskajā analīzē.
- NFA ir vairāk teorētisks jēdziens.