Teorie automatů je teoretický obor informatiky a matematiky. Je to studium abstraktních strojů a výpočetních problémů, které lze pomocí těchto strojů řešit. Abstraktní stroj se nazývá automat. Hlavní motivací rozvoje teorie automatů bylo vyvinout metody pro popis a analýzu dynamického chování diskrétních systémů.

Tento automat se skládá ze stavů a ​​přechodů. The Stát je zastoupena kruhy a Přechody je zastoupena šipky .

Automat je druh stroje, který přijímá nějaký řetězec jako vstup a tento vstup prochází konečným počtem stavů a ​​může vstoupit do konečného stavu.

Existují základní terminologie, které jsou důležité a často používané v automatech:

Symboly:

Symboly jsou entita nebo jednotlivé objekty, kterými může být jakékoli písmeno, abeceda nebo jakýkoli obrázek.

Příklad:

1, a, b, #

abecedy:

Abecedy jsou konečnou množinou symbolů. Označuje se ∑.

Příklady:

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

Tětiva:

Je to konečná sbírka symbolů z abecedy. Řetězec je označen w.

Příklad 1:

Pokud ∑ = {a, b}, různé řetězce, které lze vygenerovat z ∑, jsou {ab, aa, aaa, bb, bbb, ba, aba.....}.

• Řetězec s nulovým výskytem symbolů se nazývá prázdný řetězec. Je reprezentován ε.
• Počet symbolů v řetězci w se nazývá délka řetězce. Označuje se |w|.

Příklad 2:

 w = 010 Number of Sting |w| = 3 

Jazyk:

Jazyk je sbírka vhodných řetězců. Jazyk, který je vytvořen přes Σ, může být Konečný nebo Nekonečný .

Příklad: 1

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

Příklad: 2

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