Automatų teorija yra teorinė informatikos ir matematikos šaka. Tai yra abstrakčių mašinų ir skaičiavimo problemų, kurias galima išspręsti naudojant šias mašinas, tyrimas. Abstrakčioji mašina vadinama automatu. Pagrindinė automatų teorijos kūrimo motyvacija buvo sukurti metodus, kaip aprašyti ir analizuoti diskrečiųjų sistemų dinaminę elgseną.
Šis automatas susideda iš būsenų ir perėjimų. The valstybė atstovauja apskritimai , ir Perėjimai atstovauja rodyklėmis .
Automatas yra tokia mašina, kuri kaip įvestį paima tam tikrą eilutę ir ši įvestis pereina ribotą būsenų skaičių ir gali patekti į galutinę būseną.
Yra pagrindiniai terminai, kurie yra svarbūs ir dažnai naudojami automatuose:
Simboliai:
Simboliai yra vienetas arba atskiri objektai, kurie gali būti bet kokia raidė, abėcėlė ar bet koks paveikslėlis.
Pavyzdys:
1, a, b, #
Abėcėlės:
Abėcėlė yra baigtinis simbolių rinkinys. Jis žymimas ∑.
Pavyzdžiai:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} Eilutė:
Tai baigtinis abėcėlės simbolių rinkinys. Eilutė žymima w.
1 pavyzdys:
Jei ∑ = {a, b}, įvairios eilutės, kurias galima sugeneruoti iš ∑, yra {ab, aa, aaa, bb, bbb, ba, aba.....}.
- Eilutė, kurioje nėra simbolių, vadinama tuščia eilute. Jį pavaizduoja ε.
- Simbolių skaičius eilutėje w vadinamas eilutės ilgiu. Jis žymimas |w|.
2 pavyzdys:
w = 010 Number of Sting |w| = 3
Kalba:
Kalba yra atitinkamos eilutės rinkinys. Kalba, kuri susidaro per Σ, gali būti Baigtinis arba Begalinis .
Pavyzdys: 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> Pavyzdys: 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>