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