Automaattiteoria on tietojenkäsittelytieteen ja matematiikan teoreettinen haara. Se on abstraktien koneiden ja laskentaongelmien tutkimusta, jotka voidaan ratkaista näiden koneiden avulla. Abstraktia konetta kutsutaan automaatiksi. Automaattiteorian kehittämisen päämotivaatio oli kehittää menetelmiä diskreettien järjestelmien dynaamisen käyttäytymisen kuvaamiseksi ja analysoimiseksi.

Tämä automaatti koostuu tiloista ja siirtymistä. The Osavaltio edustaa ympyrät , ja Siirtymät edustaa nuolet .

Automaatti on sellainen kone, joka ottaa jonkin merkkijonon syötteenä ja tämä syöte kulkee äärellisen määrän tiloja läpi ja voi siirtyä lopulliseen tilaan.

On olemassa tärkeitä ja automaateissa usein käytettyjä perusterminologioita:

Symbolit:

Symbolit ovat kokonaisuuksia tai yksittäisiä objekteja, jotka voivat olla mikä tahansa kirjain, aakkoset tai mikä tahansa kuva.

Esimerkki:

1, a, b, #

Aakkoset:

Aakkoset ovat rajallinen joukko symboleja. Sitä merkitään ∑.

Esimerkkejä:

 ∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} 

Merkkijono:

Se on rajallinen kokoelma aakkosten symboleja. Merkkijono on merkitty w:llä.

Esimerkki 1:

Jos ∑ = {a, b}, eri merkkijonoja, jotka voidaan muodostaa ∑:stä, ovat {ab, aa, aaa, bb, bbb, ba, aba.....}.

• Merkkijono, jossa ei esiinny yhtään symbolia, tunnetaan tyhjänä merkkijonona. Sitä edustaa ε.
• Merkkien lukumäärää merkkijonossa w kutsutaan merkkijonon pituudeksi. Sitä merkitään |w|.

Esimerkki 2:

 w = 010 Number of Sting |w| = 3 

Kieli:

Kieli on kokoelma sopivaa merkkijonoa. Kieli, joka muodostuu Σ:n päälle, voi olla Rajallinen tai Ääretön .

Esimerkki: 1

 L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> 

Esimerkki: 2

 L2 = {Set of all strings starts with &apos;a&apos;} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>