Automat (informatica)

In informatica , soprattutto in teoria automa , un automa o un macchina astratta è il modello di un digitale , tempo discreto del computer . Se sia possibile o utile costruire effettivamente una macchina del genere è inizialmente irrilevante. La semplificazione delle capacità rende più facile capire e confrontare il comportamento di un automa.

Il termine automa gioca un ruolo centrale nell'informatica teorica . Nella teoria della computabilità e nella teoria della complessità, ad esempio, gli automi sono il concetto di calcolo sottostante. Gli automi svolgono anche un ruolo decisivo nell'informatica pratica , ad esempio nella costruzione di compilatori . Nella tecnologia digitale le macchine sono utilizzate per il controllo nei sistemi digitali e ibridi utilizzati. Tali sistemi di controllo automatico hanno applicazioni nell'architettura dei computer , nelle reti di computer e inSistemi reattivi .

Comportamento di una macchina

Il comportamento di base di una macchina è sempre lo stesso: un input come sequenza di caratteri viene presentato alla macchina dall'esterno . La macchina è in un certo stato. Ogni volta che arriva un carattere di ingresso, a seconda del carattere di ingresso e dello stato corrente , può verificarsi un nuovo stato, lo stato successivo ( transizione di stato o transizione ). L'insieme di possibili transizioni di stato che definisce il comportamento dell'automa può essere inteso come il programma dell'automa.

Automi deterministici e non deterministici

Se lo stato successivo è sempre dato in modo univoco dallo stato corrente e dal carattere di input , allora si parla di un automa deterministico . In generale, tuttavia, si può anche consentire un margine ( gradi di libertà ) per le transizioni di stato. La macchina può quindi scegliere arbitrariamente uno stato successivo da diversi possibili candidati per la stessa coppia di caratteri di stato e di input. Quindi si parla di un automa non deterministico . Il non determinismo è il benvenuto se vuoi modellare il comportamento dell'ambiente che non conosci esattamente ( non conosci ), o se vuoi lasciare le opzioni aperte per diverse implementazioni ( non importa ).

Di solito, oltre alle transizioni di stato non deterministiche, sono consentite le transizioni di stato spontanee, cioè quelle che avvengono senza caratteri di input (transizioni ε).

Macchine con e senza erogazione

Gli automi che elaborano solo le loro transizioni di stato sono anche chiamati sistemi di transizione .

Esistono anche automi che contrassegnano un certo sottoinsieme dei loro stati come stati finali . Se una parola in ingresso porta la macchina da uno stato eccellente, lo stato iniziale , a uno degli stati finali, si dice che la macchina accetti la parola in ingresso. Una tale macchina è quindi chiamata un accettore . Un accettore è adatto per definire un linguaggio formale , cioè l'insieme di tutte le parole finite che l'automa accetta.

Esistono infine anche macchine erogatrici, i cosiddetti trasduttori . Assegnate a ogni stato ( automi di Moore ) oa ciascuna coppia di caratteri di stato e di input ( automi di Mealy ) un carattere di output. In questo modo, una macchina automatica forma un'unità di elaborazione.

Classi di automi

Le macchine possono essere suddivise in classi a seconda dei mezzi a disposizione di un automa. Invece di classe di macchine, si dice anche modello di macchina . Agli accettatori della rispettiva classe può essere assegnata la lingua accettata. Risulta che ogni classe di automi corrisponde in questo modo a una classe di linguaggi formali. Ben note classi di automi sono (ciascuna con abbreviazioni per la variante deterministica e non deterministica):

Macchine di Turing (DTM / NTM)

Oltre al suo stato interno, una macchina di Turing ha anche accesso a un nastro infinito su cui una testina di lettura / scrittura mobile può scrivere caratteri e leggerli successivamente. Entrambe le classi accettano i linguaggi di tipo 0 ( linguaggio enumerabile ricorsivamente ). La macchina di Turing definisce anche il concetto di prevedibilità . Vedi la tesi di Church .

Macchine limitate lineari (DLBA / LBA)

L'unica differenza tra gli automi limitati linearmente e le macchine di Turing è che la parte accessibile della banda è limitata dalla dimensione dell'input. LBA non deterministico accetta esattamente le lingue di tipo 1 ( lingue sensibili al contesto ); la questione se ciò si applichi anche all'LBA deterministico è ancora un problema aperto.

Push macchine tasto (DPDA / PDA)

Oltre a uno di un numero finito di stati interni, una macchina seminterrato ha anche accesso al seminterrato, una pila su cui i caratteri possono essere temporaneamente memorizzati per una successiva elaborazione. I PDA accettano le lingue di tipo 2 (lingue senza contesto ). I DPDA accettano i linguaggi privi di contesto deterministici .

Macchine finite (DFA / NFA)

Un automa finito conosce solo finitamente molti stati. Entrambe le classi accettano le lingue di tipo 3 ( lingue normali ).

L'insieme degli automi è correlato agli insiemi di classi linguistiche e grammatiche come segue (vedi anche Gerarchia di Chomsky ):

Gerarchia di Chomsky	Lezione di lingua		automa non deterministico		automa deterministico
Digita 0 grammatica	${\ displaystyle {\ mathcal {\ color {blue} RE}}}$	${\ displaystyle =}$	${\ displaystyle {\ mathcal {\ color {blue} NTM}}}$	${\ displaystyle =}$	${\ displaystyle {\ mathcal {\ color {blue} DTM}}}$
Grammatica di tipo 1	${\ displaystyle {\ mathcal {\ color {blue} CS}}}$	${\ displaystyle =}$	${\ displaystyle {\ mathcal {\ color {blue} LBA}}}$	${\ displaystyle \ supseteq}$	${\ displaystyle {\ mathcal {DLBA}}}$
Grammatica di tipo 2	${\ displaystyle {\ mathcal {\ color {blue} CF}}}$	${\ displaystyle =}$	${\ displaystyle {\ mathcal {\ color {blue} PDA}}}$	${\ displaystyle \ varsupsetneq}$	${\ displaystyle {\ mathcal {DPDA}}}$
Tipo 3 grammatica	${\ displaystyle {\ mathcal {\ color {blue} REG}}}$	${\ displaystyle =}$	${\ displaystyle {\ mathcal {\ color {blue} NFA}}}$	${\ displaystyle =}$	${\ displaystyle {\ mathcal {\ color {blue} DFA}}}$

Non è ancora noto se LBA ⊃ DLBA si applichi realmente o se i DLBA accettino la stessa classe linguistica degli LBA.

Ulteriori classi di macchine sono:

Macchina a due cantine

A differenza della macchina da cantina, la macchina da due cantine ha a disposizione due cantine. Una banda di Turing può essere simulata attraverso la coppia di cantine. Le macchine a due cantine sono quindi equivalenti alle macchine di Turing. Le restrizioni sintattiche di questo modello portano alla caratterizzazione dei linguaggi di tipo 1 e di tipo 2.

Registrare le macchine

Oltre al suo stato interno, una macchina a registri ha una sequenza di registri, che sono celle di memoria per numeri naturali su cui possono essere eseguite operazioni aritmetiche elementari. Le macchine a registro sono potenti quanto le macchine di Turing.

Termini macchina estesi

Gli automi non deterministici non devono essere confusi con gli automi stocastici . I secondi assegnano probabilità alle transizioni di stato, mentre i primi parlano solo di possibilità. Pertanto, gli automi non deterministici non sono adatti per fare dichiarazioni di probabilità.

Esistono anche altri tipi di macchine che non si basano sulla lettura sequenziale di un input. Alcune delle macchine più popolari sono:

• Varianti della macchina di Turing con nastro bidimensionale o con più nastri
• Automi cellulari
• ω-automi per input infiniti
• Reti neurali
• Reti di Petri
• Modelli di calcolo algebrici

Applicazioni

Gli automi finiti e gli automi push-down sono di rilevanza pratica per la programmazione : offrono una struttura semplice con la quale molti problemi complessi possono essere risolti chiaramente. Nel compilatore, sono, ad esempio, l' implementazione dei parser utilizzati, le reazioni dei protocolli di rete spesso utilizzano una macchina a stati finiti per aggirare il loro modello di stato corrente . Le opzioni di navigazione in una procedura guidata possono anche essere espresse molto bene come un automa finito e la gestione del flusso di lavoro utilizza questi concetti per modellare i processi di lavoro.

Il modello di macchina a stati finiti viene utilizzato anche nell'implementazione di hardware sequenziale , di solito indicato come macchina a stati finiti (FSM).