Automātu teorija ir datorzinātņu un matemātikas teorētiskā nozare. Tā ir abstraktu mašīnu un skaitļošanas problēmu izpēte, ko var atrisināt, izmantojot šīs mašīnas. Abstrakto mašīnu sauc par automātiem. Automātu teorijas izstrādes galvenā motivācija bija izstrādāt metodes, lai aprakstītu un analizētu diskrētu sistēmu dinamisko uzvedību.
Šis automāts sastāv no stāvokļiem un pārejām. The Valsts pārstāv aprindās , un Pārejas pārstāv bultiņas .
Automāti ir tāda veida iekārta, kas izmanto kādu virkni kā ievadi, un šī ievade iet cauri ierobežotam stāvokļu skaitam un var nonākt galīgajā stāvoklī.
Ir galvenie termini, kas ir svarīgi un bieži tiek izmantoti automātos:
Simboli:
Simboli ir vienība vai atsevišķi objekti, kas var būt jebkurš burts, alfabēts vai jebkurš attēls.
Piemērs:
1, a, b, #
Alfabēts:
Alfabēts ir ierobežots simbolu kopums. To apzīmē ar ∑.
Piemēri:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} Virkne:
Tā ir ierobežota alfabēta simbolu kolekcija. Virkne tiek apzīmēta ar w.
1. piemērs:
Ja ∑ = {a, b}, dažādas virknes, ko var ģenerēt no ∑, ir {ab, aa, aaa, bb, bbb, ba, aba.....}.
- Virkne ar nulles simbolu gadījumiem ir pazīstama kā tukša virkne. To attēlo ε.
- Simbolu skaitu virknē w sauc par virknes garumu. To apzīmē ar |w|.
2. piemērs:
w = 010 Number of Sting |w| = 3
Valoda:
Valoda ir atbilstošas virknes kolekcija. Valoda, kas veidojas virs Σ, var būt Ierobežots vai Bezgalīgs .
Piemērs: 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> Piemērs: 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>