Teori om automater er en teoretisk gren af datalogi og matematisk. Det er studiet af abstrakte maskiner og beregningsproblemer, der kan løses ved hjælp af disse maskiner. Den abstrakte maskine kaldes automaten. Hovedmotivationen bag udviklingen af automatteorien var at udvikle metoder til at beskrive og analysere diskrete systemers dynamiske adfærd.
Denne automat består af tilstande og overgange. Det Stat er repræsenteret ved cirkler , og Overgange er repræsenteret ved pile .
Automata er den slags maskine, der tager en streng som input, og denne input går gennem et begrænset antal tilstande og kan komme ind i den endelige tilstand.
Der er de grundlæggende terminologier, der er vigtige og hyppigt brugte i automater:
Symboler:
Symboler er en enhed eller individuelle objekter, som kan være et hvilket som helst bogstav, alfabet eller et hvilket som helst billede.
Eksempel:
1, a, b, #
Alfabeter:
Alfabeter er et begrænset sæt af symboler. Det er betegnet med ∑.
Eksempler:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ}
Snor:
Det er en begrænset samling af symboler fra alfabetet. Strengen er betegnet med w.
Eksempel 1:
Hvis ∑ = {a, b}, er forskellige strenge, der kan genereres fra ∑, {ab, aa, aaa, bb, bbb, ba, aba.....}.
- En streng med nul forekomster af symboler er kendt som en tom streng. Det er repræsenteret ved ε.
- Antallet af symboler i en streng w kaldes længden af en streng. Det er betegnet med |w|.
Eksempel 2:
w = 010 Number of Sting |w| = 3
Sprog:
Et sprog er en samling af passende strenge. Et sprog som er dannet over Σ kan være Begrænset eller Uendelig .
Eksempel: 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong>
Eksempel: 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>