1. Cos'è un automa deterministico?
Un automa deterministico è un sistema matematico utilizzato per rappresentare ed elaborare un insieme di simboli. È composto da un insieme di stati, simboli e funzioni di transizione. L'automa legge un dato simbolo e, in base alle funzioni di transizione, passa a un nuovo stato.
2. Macchine a stati finiti
Una macchina a stati finiti è un tipo di automa deterministico che consiste in un insieme finito di stati e in un insieme di transizioni tra di essi. È uno strumento utile per modellare il comportamento di un sistema; può anche essere usata per progettare un programma per computer.
3. Rappresentazioni a stati finiti
Per rappresentare una macchina a stati finiti, dobbiamo definire l'insieme degli stati e le transizioni tra di essi. Ogni stato è tipicamente rappresentato da un numero o da un simbolo e le transizioni tra gli stati possono essere rappresentate da frecce con etichette.
4. Automi finiti deterministici (DFA)
Un automa finito deterministico (DFA) è un tipo speciale di macchina a stati finiti. Consiste in un insieme finito di stati e in un insieme di transizioni tra di essi che sono completamente determinati dallo stato corrente e dal simbolo di ingresso.
5. Un automa finito non deterministico (NFA)
Un automa finito non deterministico (NFA) è un tipo di macchina a stati finiti che consente transizioni multiple da uno stato all'altro. A differenza di un DFA, un NFA può avere più transizioni per un dato simbolo di ingresso.
6. Funzioni di transizione
Una funzione di transizione è un insieme di regole che determinano in quale stato l'automa deve passare quando viene letto un particolare simbolo di ingresso. La funzione di transizione è definita da un insieme di coppie (stato, simbolo), dove il primo elemento della coppia è lo stato corrente e il secondo è il simbolo di ingresso.
7. Rappresentazione grafica degli automi
La rappresentazione grafica di un automa è uno strumento utile per comprenderne il comportamento. Consiste in un insieme di cerchi, ciascuno dei quali rappresenta uno stato, e di frecce che collegano gli stati, che rappresentano le transizioni tra di essi.
8. Esempi di automi deterministici
Gli automi deterministici sono utilizzati in molte applicazioni, come il riconoscimento di modelli, l'elaborazione del linguaggio e la visione artificiale. Esempi di automi deterministici sono le macchine a stati finiti, gli automi pushdown e le macchine di Turing.
Gli automi deterministici sono automi che hanno una transizione unica per ogni simbolo di ingresso. Ciò significa che l'automa può trovarsi in un solo stato per un dato simbolo di ingresso. Gli automi non deterministici sono automi che hanno più transizioni per ogni simbolo di ingresso. Ciò significa che l'automa può trovarsi in più stati per un dato simbolo di ingresso.
Gli automi finiti deterministici (DFA) sono un tipo di automi finiti che accettano o rifiutano una data stringa di simboli in base a un insieme fisso di regole. In altre parole, i DFA producono sempre lo stesso output per un dato input.
Un esempio di DFA è un semplice semaforo. Cambierà sempre da verde a giallo a rosso e poi di nuovo a verde, indipendentemente dal numero di volte in cui viene avviato. Un altro esempio è un distributore automatico; per un dato input (ad esempio un certo numero di monete) erogherà sempre lo stesso prodotto.
Gli input che non rientrano nelle regole della macchina (ad esempio, l'inserimento di un numero eccessivo o insufficiente di monete) faranno sì che la macchina non funzioni o produca un errore.
I quattro tipi di automi sono:
1. Automi finiti
2.
2. Automi a spinta
3. Automi a limiti lineari
4. Macchine di Turing
Deterministico vs probabilistico si riferisce al grado di certezza con cui un evento si verificherà. Un evento deterministico è un evento che si verificherà con una certezza del 100%, mentre un evento probabilistico è un evento che può verificarsi o meno, con un certo grado di incertezza.
Un esempio deterministico è un esempio che produce sempre lo stesso risultato, dato lo stesso input. Ad esempio, se si mettono sempre due cucchiai di zucchero nel caffè, si otterrà sempre un caffè più dolce di due cucchiai rispetto a quello che si sarebbe ottenuto mettendo un cucchiaio di zucchero.