Theory of automata är en teoretisk gren av datavetenskap och matematisk. Det är studiet av abstrakta maskiner och beräkningsproblem som kan lösas med dessa maskiner. Den abstrakta maskinen kallas automaten. Den främsta motivationen bakom utvecklingen av automatateorin var att utveckla metoder för att beskriva och analysera det dynamiska beteendet hos diskreta system.
Denna automat består av tillstånd och övergångar. De stat representeras av cirklar , och den Övergångar representeras av pilar .
Automata är den typ av maskin som tar någon sträng som indata och denna ingång går igenom ett ändligt antal tillstånd och kan komma in i det slutliga tillståndet.
Det finns de grundläggande terminologierna som är viktiga och ofta används i automater:
Symboler:
Symboler är en enhet eller enskilda objekt, som kan vara vilken bokstav, alfabet eller vilken bild som helst.
Exempel:
1, a, b, #
Alfabet:
Alfabet är en ändlig uppsättning symboler. Det betecknas med ∑.
Exempel:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} Sträng:
Det är en ändlig samling symboler från alfabetet. Strängen betecknas med w.
Exempel 1:
Om ∑ = {a, b} är olika strängar som kan genereras från ∑ {ab, aa, aaa, bb, bbb, ba, aba.....}.
- En sträng med noll förekomster av symboler kallas en tom sträng. Den representeras av ε.
- Antalet symboler i en sträng w kallas längden på en sträng. Det betecknas med |w|.
Exempel 2:
w = 010 Number of Sting |w| = 3
Språk:
Ett språk är en samling lämpliga strängar. Ett språk som bildas över Σ kan vara Ändlig eller Oändlig .
Exempel: 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> Exempel: 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>