Teorija avtomatov je teoretična veja računalništva in matematike. To je preučevanje abstraktnih strojev in računskih problemov, ki jih je mogoče rešiti z uporabo teh strojev. Abstraktni stroj se imenuje avtomati. Glavna motivacija za razvoj teorije avtomatov je bil razvoj metod za opisovanje in analizo dinamičnega obnašanja diskretnih sistemov.
Ta avtomat je sestavljen iz stanj in prehodov. The Država predstavlja krogih , in Prehodi predstavlja puščice .
Avtomat je vrsta stroja, ki sprejme nekaj niza kot vhod in ta vhod gre skozi končno število stanj in lahko vstopi v končno stanje.
Obstajajo osnovne terminologije, ki so pomembne in se pogosto uporabljajo v avtomatih:
Simboli:
Simboli so entitete ali posamezni predmeti, ki so lahko katera koli črka, abeceda ali katera koli slika.
primer:
1, a, b, #
abecede:
Abecede so končen niz simbolov. Označena je z ∑.
Primeri:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} Vrvica:
Je končna zbirka simbolov iz abecede. Niz je označen z w.
Primer 1:
Če je ∑ = {a, b}, so različni nizi, ki jih je mogoče ustvariti iz ∑, {ab, aa, aaa, bb, bbb, ba, aba.....}.
- Niz z nič pojavitvami simbolov je znan kot prazen niz. Predstavljena je z ε.
- Število simbolov v nizu w imenujemo dolžina niza. Označena je z |w|.
Primer 2:
w = 010 Number of Sting |w| = 3
jezik:
Jezik je zbirka ustreznega niza. Jezik, ki je oblikovan nad Σ, je lahko Končno oz Neskončno .
Primer: 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> Primer: 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>