La teoria dels autòmats és una branca teòrica de la informàtica i les matemàtiques. És l'estudi de les màquines abstractes i els problemes de càlcul que es poden resoldre amb aquestes màquines. La màquina abstracta s'anomena autòmat. La principal motivació darrere del desenvolupament de la teoria dels autòmats va ser desenvolupar mètodes per descriure i analitzar el comportament dinàmic de sistemes discrets.

Aquest autòmat consta d'estats i transicions. El Estat està representat per cercles , i la Transicions està representat per fletxes .

Els autòmats són el tipus de màquina que pren una cadena com a entrada i aquesta entrada passa per un nombre finit d'estats i pot entrar a l'estat final.

Hi ha les terminologies bàsiques que són importants i que s'utilitzen freqüentment en autòmats:

Símbols:

Els símbols són una entitat o objectes individuals, que poden ser qualsevol lletra, alfabet o qualsevol imatge.

Exemple:

1, a, b, #

Alfabets:

Els alfabets són un conjunt finit de símbols. Es denota amb ∑.

Exemples:

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

Cadena:

És una col·lecció finita de símbols de l'alfabet. La cadena es denota amb w.

Exemple 1:

Si ∑ = {a, b}, diverses cadenes que es poden generar a partir de ∑ són {ab, aa, aaa, bb, bbb, ba, aba.....}.

• Una cadena amb zero aparicions de símbols es coneix com una cadena buida. Es representa per ε.
• El nombre de símbols d'una cadena w s'anomena longitud d'una cadena. Es denota amb |w|.

Exemple 2:

 w = 010 Number of Sting |w| = 3 

Llenguatge:

Un llenguatge és una col·lecció de cadenes apropiades. Un llenguatge que es forma sobre Σ pot ser Finit o Infinit .

Exemple: 1

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

Exemple: 2

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