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 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>