Теорија аутомата је теоријска грана рачунарства и математике. То је проучавање апстрактних машина и рачунских проблема који се могу решити помоћу ових машина. Апстрактна машина се назива аутоматима. Главна мотивација за развој теорије аутомата била је развој метода за описивање и анализу динамичког понашања дискретних система.
Овај аутомат се састоји од стања и прелаза. Тхе Држава представља круговима , анд тхе Транситионс представља стрелице .
Аутомати су врста машине која узима неки низ као улаз и овај улаз пролази кроз коначан број стања и може ући у коначно стање.
Постоје основне терминологије које су важне и које се често користе у аутоматима:
Симболи:
Симболи су ентитет или појединачни објекти, који могу бити било које слово, абецеда или било која слика.
Пример:
1, а, б, #
абецеде:
Абецеде су коначан скуп симбола. Означава се са ∑.
Примери:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} Низ:
То је коначан скуп симбола из абецеде. Низ је означен са в.
Пример 1:
Ако је ∑ = {а, б}, различити низови који се могу генерисати из ∑ су {аб, аа, ааа, бб, ббб, ба, аба.....}.
- Низ са нула појављивања симбола је познат као празан стринг. Представљен је са ε.
- Број симбола у низу в назива се дужина низа. Означава се са |в|.
Пример 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 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>