Teória automatov je teoretický odbor informatiky a matematiky. Je to štúdium abstraktných strojov a výpočtových problémov, ktoré možno pomocou týchto strojov vyriešiť. Abstraktný stroj sa nazýva automat. Hlavnou motiváciou vývoja teórie automatov bolo vyvinúť metódy na opis a analýzu dynamického správania diskrétnych systémov.

Tento automat pozostáva zo stavov a prechodov. The Štát je zastúpený kruhy , a Prechody je zastúpený šípky .

Automat je typ stroja, ktorý berie ako vstup nejaký reťazec a tento vstup prechádza konečným počtom stavov a môže vstúpiť do konečného stavu.

Existujú základné terminológie, ktoré sú dôležité a často používané v automatoch:

Symboly:

Symboly sú entita alebo jednotlivé objekty, ktoré môžu byť ľubovoľné písmeno, abeceda alebo akýkoľvek obrázok.

Príklad:

1, a, b, #

abecedy:

Abecedy sú konečnou množinou symbolov. Označuje sa ∑.

Príklady:

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

Reťazec:

Je to konečná zbierka symbolov z abecedy. Reťazec je označený w.

Príklad 1:

Ak ∑ = {a, b}, rôzne reťazce, ktoré možno vygenerovať z ∑, sú {ab, aa, aaa, bb, bbb, ba, aba.....}.

• Reťazec s nulovým výskytom symbolov je známy ako prázdny reťazec. Je reprezentovaný ε.
• Počet symbolov v reťazci w sa nazýva dĺžka reťazca. Označuje sa |w|.

Príklad 2:

 w = 010 Number of Sting |w| = 3 

Jazyk:

Jazyk je kolekcia vhodných reťazcov. Jazyk, ktorý je vytvorený nad Σ môže byť Konečný alebo Nekonečné .

Príklad: 1

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

Príklad: 2

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