Teorija automata je teorijska grana računalne znanosti i matematike. To je proučavanje apstraktnih strojeva i računalnih problema koji se mogu riješiti pomoću tih strojeva. Apstraktni stroj naziva se automat. Glavna motivacija iza razvoja teorije automata bila je razvijanje metoda za opisivanje i analizu dinamičkog ponašanja diskretnih sustava.
Ovaj automat se sastoji od stanja i prijelaza. The država predstavlja ga krugovi , i Prijelazi predstavlja ga strijele .
Automat je vrsta stroja koji uzima neki niz kao ulaz i taj ulaz prolazi kroz konačan broj stanja i može ući u konačno stanje.
Postoje osnovne terminologije koje su važne i često korištene u automatima:
Simboli:
Simboli su entitet ili pojedinačni objekti, koji mogu biti bilo koje slovo, abeceda ili bilo koja slika.
Primjer:
1, a, b, #
abecede:
Abecede su konačan skup simbola. Označava se s ∑.
Primjeri:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} Niz:
To je konačna zbirka simbola iz abecede. Niz je označen s w.
Primjer 1:
Ako je ∑ = {a, b}, različiti nizovi koji se mogu generirati iz ∑ su {ab, aa, aaa, bb, bbb, ba, aba.....}.
- Niz s nula pojavljivanja simbola poznat je kao prazan niz. Predstavlja se s ε.
- Broj simbola u nizu w naziva se duljina niza. Označava se sa |w|.
Primjer 2:
w = 010 Number of Sting |w| = 3
Jezik:
Jezik je kolekcija odgovarajućeg niza. Jezik koji se formira nad Σ može biti Konačan ili Beskonačno .
Primjer: 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> Primjer: 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>