La teoria degli automi è una branca teorica dell'informatica e della matematica. È lo studio delle macchine astratte e dei problemi di calcolo che possono essere risolti utilizzando queste macchine. La macchina astratta si chiama automa. La motivazione principale alla base dello sviluppo della teoria degli automi era lo sviluppo di metodi per descrivere e analizzare il comportamento dinamico dei sistemi discreti.
Questo automa è costituito da stati e transizioni. IL Stato è rappresentato da cerchi , e il Transizioni è rappresentato da frecce .
Gli automi sono il tipo di macchina che accetta una stringa come input e questo input passa attraverso un numero finito di stati e può entrare nello stato finale.
Esistono le terminologie di base importanti e utilizzate frequentemente negli automi:
Simboli:
I simboli sono un'entità o singoli oggetti, che possono essere qualsiasi lettera, alfabeto o qualsiasi immagine.
Esempio:
1, a, b, #
Alfabeti:
Gli alfabeti sono un insieme finito di simboli. È indicato con ∑.
Esempi:
∑ = {a, b} ∑ = {A, B, C, D} ∑ = {0, 1, 2} ∑ = {0, 1, ....., 5] ∑ = {#, β, Δ} Corda:
È una raccolta finita di simboli dell'alfabeto. La stringa è indicata con w.
Esempio 1:
Se ∑ = {a, b}, le varie stringhe che si possono generare da ∑ sono {ab, aa, aaa, bb, bbb, ba, aba.....}.
- Una stringa con zero occorrenze di simboli è detta stringa vuota. È rappresentato da ε.
- Il numero di simboli in una stringa w è chiamato lunghezza di una stringa. Si indica con |w|.
Esempio 2:
w = 010 Number of Sting |w| = 3
Lingua:
Una lingua è una raccolta di stringhe appropriate. Una lingua che si forma su Σ può esserlo Finito O Infinito .
Esempio 1
L1 = {Set of string of length 2} = {aa, bb, ba, bb} <strong>Finite Language</strong> Esempio: 2
L2 = {Set of all strings starts with 'a'} = {a, aa, aaa, abb, abbb, ababb} <strong>Infinite Language</strong>