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 &apos;a&apos;} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>