Nell'era tecnologica odierna, sia l'hardware che il software hanno visto uno sviluppo enorme. Una delle principali aree di sviluppo è stata vista nei metodi di progettazione hardware. Con il tecnologia in crescita , è stato possibile implementare il concetto di co-design hardware - software. Vengono sviluppati diversi metodi mediante i quali, utilizzando il software si può progettare e simulare completamente i sistemi hardware. Uno di questi metodi è la teoria degli automi. La teoria degli automi è il ramo di informatica che si occupa di progettare il modello astratto di dispositivi informatici che seguono automaticamente la sequenza di passaggi predeterminata. Questo articolo discute brevi informazioni sul tutorial sugli automi.
Cos'è la teoria degli automi?
La parola automi deriva dal greco, che significa 'auto-agente'. Un automa è un modello matematico della macchina. L'automa è costituito da stati e transizioni. Quando l'input è dato all'automa, effettua una transizione allo stato successivo, a seconda della funzione di transizione. Gli ingressi alla funzione di transizione sono lo stato presente e i simboli recenti. Se un automa ha un numero finito di stati, è noto come automi finiti o Macchina a stati finiti . Gli automi finiti sono rappresentati da una tupla di 5 (Q, ∑, δ, qo, F)
Dove,
Q = insieme finito di stati.
∑ = insieme finito di simboli chiamato anche Alfabeto degli automi.
δ = la funzione di transizione.
qo = stato iniziale dell'ingresso.
F = insieme degli stati finali di Q.
Terminologie di base della teoria degli automi
Alcune delle terminologie di base della Teoria degli automi sono:
1 . Alfabeto : Qualsiasi insieme finito di simboli nella teoria degli automi è noto come alfabeto. Rappresentato dalla lettera l'insieme {a, b, c, d, e,} è chiamato insieme dell'alfabeto, mentre le lettere dell'insieme 'a', 'b', 'c', 'd', 'e' sono chiamate simboli.
Due . Corda : Negli automi, una stringa è una sequenza finita di simboli presi dall'insieme alfabetico ∑, Ad esempio, la stringa S = 'adeaddadc' è valida sull'insieme alfabetico = {a, b, c, d, e,}.
3 . Lunghezza della stringa : Il numero di simboli presenti nella stringa è noto come Lunghezza della stringa. Per la stringa S = 'adaada' la lunghezza della stringa è | S | = 6. Se la lunghezza della stringa è 0, viene chiamata stringa vuota.
4 . Kleen Star : È l'operatore unario sull'insieme dei simboli Σ, che fornisce l'insieme infinito di tutte le possibili stringhe, inclusa λ, di tutte le lunghezze possibili sull'insieme Σ. È rappresentato da. Ad esempio, per l'insieme Σ = {c, d}, ∑ * = {λ, c, d, cd, dc, cc, dd, ……}.
5 . Chiusura Kleen : È l'insieme infinito di tutte le possibili stringhe del set alfabetico escluso λ. È indicato da. Per l'insieme Σ = {a, d}, ∑ + = {a, d, ad, da, aa, dd,… ..}.
6 . linguaggio : La lingua è il sottoinsieme del set di stelle Kleene∑ * per alcuni set di alfabeto Σ. Il linguaggio può essere finito o infinito. Ad esempio, se una lingua accetta tutte le possibili stringhe di lunghezza 2 sull'insieme Σ = {a, d}, allora L = {aa, ad, da, dd}.
Linguaggi formali e automi
Nella teoria degli automi, il linguaggio formale è un insieme di stringhe, dove si trova ogni stringa composto da simboli appartenente all'insieme finito Alfabeto Σ. Consideriamo un linguaggio felino, che può contenere qualsiasi stringa dal set infinito sottostante ...
miagolare!
meww!
mewww !! ……
Il set alfabetico per la lingua dei gatti è Σ = {m, e, w,!}. Lascia che questo set venga utilizzato per un modello di automi a stati finiti-m. Quindi il linguaggio formale caratterizzato dal modello m è indicato con
L (m)
L (m) = {'mew!', 'Meww!', 'Mewww', ……}
L'automa è utile per definire una lingua perché può esprimere un insieme infinito in una forma chiusa. Le lingue formali non sono le stesse lingue naturali che parliamo nella nostra vita quotidiana. Un linguaggio formale può denotare i diversi stati della macchina, a differenza dei nostri linguaggi regolari. Il linguaggio formale viene utilizzato per modellare una parte del linguaggio naturale come la sintassi, ecc ... I linguaggi formali sono definiti da automi a stati finiti. Ci sono due prospettive principali degli automi a stati finiti: gli Acceptors possono dire se una stringa è nella lingua e la seconda è il generatore che produce solo le stringhe nella lingua.
Automi finiti deterministici
Nel tipo deterministico di automi, quando viene fornito un input, possiamo sempre determinare in quale stato sarebbe la transizione. Poiché si tratta di un automa finito, si chiama Automi Finiti Deterministici.
Rappresentazione grafica
Il diagramma di stato è il digrafo utilizzato per la rappresentazione grafica degli automi finiti deterministici. Cerchiamo di capire con un esempio. Lascia che gli automi finiti deterministici siano ...
Q = {a, b, c, d}.
Σ = {0, 1}
= {a}
F = {d} e la funzione di transizione be
Rappresentazione grafica in forma tabulare
Diagramma di stato
Diagramma di stato degli automi deterministici a stati finiti
Dal diagramma di stato
- Gli stati sono rappresentati da vertici.
- Le transizioni sono rappresentate dall'arco etichettato con un alfabeto di input.
- Il singolo arco in entrata vuoto rappresenta lo stato iniziale.
- Lo stato con i doppi cerchi è lo stato finale.
Automi finiti non deterministici
Gli automi in cui non è possibile determinare lo stato dell'output per un dato input sono chiamati automi non deterministici. È anche chiamato automi finiti non deterministici, poiché ha un numero finito di stati. Gli automi finiti non deterministici sono rappresentati come l'insieme di 5 -tuple dove (Q, ∑, δ, qo, F)
Q = insieme finito di stati.
∑ = Set di alfabeto.
δ = la funzione di transizione
dove : 
qo = Stato iniziale.
Rappresentazione grafica
Gli automi finiti non deterministici sono rappresentati con l'aiuto del diagramma di stato. Lascia che gli automi finiti non deterministici siano
Q = {a, b, c, d}
Σ = {0,1}
qo = {a}
F = {d}
Le transizioni sono
Rappresentazione grafica in forma tabulare
Diagramma di stato
Diagramma di stato degli automi finiti non deterministici
Applicazioni della teoria degli automi
Le applicazioni di teoria degli automi include il seguente.
- La teoria degli automi è molto utile nei campi della teoria del calcolo, produzioni di compilatori, intelligenza artificiale, ecc.
- Per i compilatori di elaborazione del testo e i progetti hardware, gli automi finiti giocano un ruolo importante.
- Per applicazioni in AI e in linguaggi di programmazione , La grammatica libera dal contesto è molto utile.
- Nel campo della biologia, gli automi cellulari sono utili.
- Anche nella teoria dei campi finiti possiamo trovare l'applicazione degli automi.
In questo articolo, abbiamo imparato una breve introduzione ai linguaggi e al calcolo della teoria degli automi. Gli automi esistono sin dal periodo preistorico. Con l'invenzione di nuove tecnologie si vedono molti nuovi sviluppi in questo campo. Con che tipo di automi ti sei imbattuto?
