logo

Teori om automater

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