Теорията на автоматите е теоретичен клон на компютърните науки и математиката. Това е изучаването на абстрактни машини и изчислителните проблеми, които могат да бъдат решени с помощта на тези машини. Абстрактната машина се нарича автомати. Основната мотивация зад разработването на теорията на автоматите беше да се разработят методи за описание и анализ на динамичното поведение на дискретни системи.

Този автомат се състои от състояния и преходи. The състояние се представлява от кръгове , и Преходи се представлява от стрелки .

Automata е вид машина, която приема някакъв низ като вход и този вход преминава през краен брой състояния и може да влезе в крайното състояние.

Има основните терминологии, които са важни и често използвани в автоматите:

Символи:

Символите са същност или отделни обекти, които могат да бъдат всяка буква, азбука или изображение.

Пример:

1, а, б, #

Азбуки:

Азбуките са краен набор от символи. Означава се с ∑.

Примери:

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

низ:

Това е ограничена колекция от символи от азбуката. Низът се обозначава с w.

Пример 1:

Ако ∑ = {a, b}, различните низове, които могат да бъдат генерирани от ∑, са {ab, aa, aaa, bb, bbb, ba, aba.....}.

• Низ с нула срещания на символи е известен като празен низ. Той е представен с ε.
• Броят на символите в низ w се нарича дължина на низ. Означава се с |w|.

Пример 2:

 w = 010 Number of Sting |w| = 3 

език:

Езикът е колекция от подходящ низ. Език, който се формира върху Σ, може да бъде Краен или Безкраен .

Пример: 1

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

Пример: 2

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