Teoria degli automi, automi finiti
La struttura, il design, il principio di funzionamento di varie macchine sono in gran parte determinati dal suo scopo funzionale. Distinguere tra macchine tecnologiche, di trasporto, informatiche, militari e di altro tipo. Interi complessi automatici progettati per eseguire processi tecnologici complessi sono ampiamente introdotti in vari settori. Gli automi sono progettati e costruiti che svolgono varie funzioni logiche (macchine logiche).
Teoria degli automi — sezione cibernetica, sorto sotto l'influenza dei requisiti della tecnologia dei computer digitali e delle macchine di controllo. Gli automi discreti studiati nella teoria degli automi sono modelli astratti di sistemi reali (sia tecnici che biologici) che elaborano informazioni discrete (digitali) in fasi temporali discrete.
La teoria degli automi si basa su precisi concetti matematici che formalizzano idee intuitive sul funzionamento (comportamento) dell'automa e sulla sua struttura (struttura interna).
In questo caso, la trasformazione delle informazioni è sempre intesa come un'operazione che trasforma sequenze di input composte da lettere dell'alfabeto di input in sequenze di output composte da lettere dell'alfabeto di output.
L'apparato di logica matematica, algebra, teoria della probabilità, calcolo combinatorio e teoria dei grafi è ampiamente utilizzato.
Il problema con la teoria degli automi in alcune delle sue parti (teoria strutturale degli automi) è cresciuto dalla teoria dei circuiti di contatto a relè, che iniziò a prendere forma alla fine degli anni '30. inclusivo metodi di algebra logica.
Nella teoria strutturale degli automi vengono studiati diversi tipi di schemi, progettati per descrivere come un automa complesso viene creato da componenti (elementi) più semplici opportunamente collegati in un sistema.
Un'altra direzione, chiamata teoria astratta degli automi, studia il comportamento degli automi (ovvero la natura della trasformazione delle informazioni da essi effettuata), astraendo dalle specificità della loro struttura interna, e nata negli anni '50.
Nell'ambito della teoria astratta degli automi, il contenuto dei concetti "automa" e "macchina" è essenzialmente esaurito dalla descrizione standard della trasformazione dell'informazione che viene effettuata da un automa. Tale trasformazione può essere deterministica, ma può anche essere di natura probabilistica.
Le più studiate sono le macchine deterministiche (automi), che includono gli automi finiti, il principale oggetto di studio nella teoria degli automi.
Una macchina a stati finiti è caratterizzata da una quantità limitata di memoria (il numero di stati interni) ed è definita utilizzando una funzione di transizione.Con una ragionevole idealizzazione, tutte le moderne macchine matematiche e persino il cervello, dal punto di vista del loro funzionamento, possono essere considerati automi finiti.
I termini "macchina sequenziale", "automa di Milly", "automa di Moore" sono usati in letteratura (e non uniformemente da tutti gli autori) come sinonimi del termine "automa finito" o per sottolineare alcune caratteristiche nelle funzioni di transizione di un oggetto finito automa.
Gli automi con memoria illimitata sono una macchina di Turing in grado di eseguire (potenzialmente) qualsiasi trasformazione efficiente delle informazioni. Il concetto di "macchina di Turing" è nato prima del concetto di "macchina a stati finiti" ed è studiato principalmente nella teoria degli algoritmi.
La teoria degli automi astratti è strettamente correlata alle ben note teorie algebriche, ad esempio la teoria dei semigruppi. Da un punto di vista applicativo, sono interessanti i risultati che caratterizzano la trasformazione delle informazioni in un automa in termini di dimensione della memoria.
Questo è il caso, ad esempio, nei problemi con esperimenti sugli automi (opere di E.F. Moore, ecc.), dove l'una o l'altra informazione sulle funzioni di transizione dell'automa o sulla capacità della sua memoria è ottenuta dai risultati della esperimenti.
Un altro compito è calcolare i periodi delle sequenze di output, in base alle informazioni disponibili sulla dimensione della memoria dell'automa e sui periodi delle sequenze di input.
Di grande importanza è lo sviluppo di metodi per minimizzare la memoria di macchine a stati finiti e studiarne il comportamento in ambienti casuali.
Nella teoria degli automi astratti, il problema di sintesi è il seguente.In termini di un linguaggio chiaramente formalizzato, le condizioni sono scritte per il comportamento dell'automa progettato (per l'evento rappresentato nell'automa). In questo caso, è necessario sviluppare metodi che in base a ciascuna condizione scritta:
1) scoprire se esiste una macchina a stati tale che l'informazione da essa trasformata soddisfi questa condizione;
2) in caso affermativo, vengono costruite le funzioni di transizione di tale macchina a stati finiti o viene stimata la dimensione della sua memoria.
La soluzione del compito di sintesi in una tale formulazione presuppone la creazione preliminare di un linguaggio conveniente per registrare le condizioni operative di un automa con algoritmi convenienti per il passaggio dalla registrazione alle funzioni transitive.
Nella teoria strutturale degli automi, il problema della sintesi consiste nel costruire una catena di elementi di un dato tipo che realizzi un automa finito dato dalle sue funzioni di transizione. In questo caso, di solito stabiliscono alcuni criteri di ottimalità (ad esempio, il numero minimo di elementi) e cercano di ottenere uno schema ottimale.
Come si è scoperto in seguito, ciò significa che alcuni dei metodi e dei concetti sviluppati in precedenza in relazione ai circuiti di contatto a relè sono applicabili a circuiti di altro tipo.
In connessione con lo sviluppo delle tecnologie elettroniche, i più diffusi sono gli schemi di elementi funzionali (reti logiche). Un caso speciale di reti logiche sono le reti neurali astratte, i cui elementi sono chiamati neuroni.
Sono stati sviluppati molti metodi di sintesi, a seconda del tipo di circuiti e della trasformazione delle informazioni a cui sono destinati (Sintesi di dispositivi a relè).
Aspetto -Minimizzazione di circuiti combinatori, mappe di Carnot, sintesi circuitale
Macchina a stati finiti — un modello matematico di un sistema di controllo con una dimensione di memoria fissa (incapace di aumentare durante il funzionamento).
Il concetto di macchina a stati finiti è un'astrazione matematica che caratterizza le caratteristiche generali di un insieme di sistemi di controllo (ad esempio, un dispositivo relè multi-loop). Tutti questi sistemi hanno caratteristiche comuni che è naturale accettare come definizione di un automa finito.
Ogni automa completato ha un ingresso esposto alle influenze esterne e agli elementi interni. Sia per gli elementi di input che per quelli interni, esiste un numero fisso di stati discreti che possono assumere.
Il cambiamento negli stati dell'input e degli elementi interni avviene in momenti discreti nel tempo, gli intervalli tra i quali sono chiamati tick. Lo stato interno (lo stato degli interni) alla fine del nastro è determinato interamente dallo stato interno e dallo stato dell'ingresso all'inizio del nastro.
Tutte le altre definizioni di automa finito possono essere ridotte a questa caratteristica, in particolare le definizioni che presumono che un automa finito abbia un'uscita che dipende dallo stato interno dell'automa in un dato momento.
In termini di tale caratteristica, la natura dei suoi input e stati interni è irrilevante per la descrizione di un automa completo. Invece di input e stati, puoi semplicemente guardare i loro numeri in una numerazione casuale.
La macchina a stati verrà impostata se viene specificata la dipendenza del suo numero di stato interno dal numero di stato interno precedente e dal numero di stato di input precedente. Tale compito può essere sotto forma di un tavolo finale.
Un altro modo comune per definire un automa completo è la costruzione del cosiddetto diagrammi di transizione. Gli stati di input sono spesso chiamati semplicemente input e gli stati interni sono semplicemente stati.
Una macchina a stati finiti può essere un modello sia di dispositivi tecnici che di alcuni sistemi biologici. Gli automi del primo tipo sono, ad esempio, dispositivi a relè e vari computer elettronici, incl. controllori logici programmabili.
Nel caso di un dispositivo a relè, il ruolo degli stati di ingresso è svolto dalle combinazioni di stati degli elementi sensibili del dispositivo a relè (ogni combinazione di tali stati è uno «stato complesso», caratterizzato dall'indicazione di tutti gli elementi sensibili di questi stati discreti che hanno in un dato momento). Allo stesso modo, combinazioni di stati di elementi intermedi di un dispositivo a relè agiscono come stati interni.
Un controllore logico programmabile (PLC) è un esempio di un dispositivo di azione relè che può essere definito una macchina a stati autonoma.
Infatti, una volta che il programma è stato inserito nel PLC e il controllore ha iniziato a calcolare, non è esposto ad influenze esterne ed ogni stato successivo è completamente determinato dal suo stato precedente. Possiamo supporre che l'ingresso abbia lo stesso stato in ogni ciclo di clock.
Al contrario, qualsiasi macchina a stati finiti che abbia l'unico stato di input possibile è naturalmente chiamata autonoma, poiché in questo caso l'ambiente esterno non porta alcuna informazione che ne controlli il comportamento.
Guarda anche:
L'uso di sistemi a microprocessore nell'ingegneria elettrica sull'esempio dell'uso del PLC