Teoria automatelor este o ramură teoretică a informaticii și matematicii. Este studiul mașinilor abstracte și al problemelor de calcul care pot fi rezolvate folosind aceste mașini. Mașina abstractă se numește automate. Principala motivație din spatele dezvoltării teoriei automatelor a fost dezvoltarea unor metode de a descrie și analiza comportamentul dinamic al sistemelor discrete.
Acest automat este format din stări și tranziții. The Stat este reprezentat de cercuri , si Tranziții este reprezentat de săgeți .
Automatele sunt genul de mașină care ia un șir ca intrare și această intrare trece printr-un număr finit de stări și poate intra în starea finală.
Există terminologii de bază care sunt importante și utilizate frecvent în automate:
Simboluri:
Simbolurile sunt o entitate sau obiecte individuale, care pot fi orice literă, alfabet sau orice imagine.
Exemplu:
1, a, b, #
Alfabete:
Alfabetele sunt un set finit de simboluri. Se notează cu ∑.
Exemple:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} Şir:
Este o colecție finită de simboluri din alfabet. Șirul este notat cu w.
Exemplul 1:
Dacă ∑ = {a, b}, diverse șiruri care pot fi generate din ∑ sunt {ab, aa, aaa, bb, bbb, ba, aba.....}.
- Un șir cu zero apariții de simboluri este cunoscut ca șir gol. Este reprezentat prin ε.
- Numărul de simboluri dintr-un șir w se numește lungimea unui șir. Se notează cu |w|.
Exemplul 2:
w = 010 Number of Sting |w| = 3
Limba:
O limbă este o colecție de șiruri adecvate. Un limbaj care se formează peste Σ poate fi Finit sau Infinit .
Exemplu: 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> Exemplu: 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>