Automi a stati finiti

Esercizio 1: Creazione di un Semaforo a Stati Finiti

Obiettivo: Creare un automa a stati finiti che rappresenti il comportamento di un semaforo stradale.

Istruzioni dettagliate:

1. Definisci gli stati: Identifica gli stati necessari per rappresentare un semaforo, ad esempio, "Rosso," "Giallo," e "Verde."

2. Definisci gli input: Specifica gli input che influenzano il cambio di stato dell'automa, come "Passaggio pedonale" e "Tempo scaduto."

3. Creazione del diagramma: Disegna un diagramma dell'automa a stati finiti, rappresentando ciascuno stato con un cerchio e collegando gli stati con frecce etichettate con gli input corrispondenti.

4. Definizione delle regole: Spiega le regole per le transizioni di stato. Ad esempio, quando ricevi l'input "Passaggio pedonale" dallo stato "Rosso," l'automa dovrebbe transizionare a "Verde."

5. Test dell'automa: Esegui simulazioni utilizzando input simulati per verificare che l'automa si comporti secondo lo standard di funzionamento di un semaforo.

Esercizio 2: Riconoscimento di Sequenze Numeriche

Obiettivo: Creare un automa a stati finiti che riconosca sequenze con almeno due zeri consecutivi.

Istruzioni dettagliate:

1. Definisci il modello di sequenza: Specifica il tipo di sequenza numerica che l'automa deve riconoscere, come sequenze con almeno due zeri consecutivi.

2. Creazione del diagramma: Disegna un diagramma dell'automa a stati finiti. Gli stati dovrebbero rappresentare il progresso nella lettura della sequenza numerica, e le transizioni di stato dovrebbero basarsi sui numeri letti dall'input.

3. Definizione delle regole: Descrivi le regole per le transizioni di stato. Per esempio, quando leggi "0" nello stato iniziale, vai a uno stato in cui aspetti il prossimo simbolo. Se incontri un altro "0," vai a uno stato di accettazione.

4. Test dell'automa: Utilizza diverse sequenze numeriche come input per verificare che l'automa riconosca correttamente le sequenze specificate.

Esercizio 3: Riconoscimento di Sequenze di Parentesi Bilanciate

1. Obiettivo: L'obiettivo di questo esercizio è creare un automa a stati finiti che riconosca sequenze di parentesi bilanciate. Ad esempio, "(())" e "()" sono sequenze bilanciate, mentre "())" e "(" non lo sono.

2. Istruzioni dettagliate:

   • Definisci il modello di sequenza: Decide il tipo di sequenza di parentesi che l'automa deve riconoscere. Ad esempio, potresti voler riconoscere sequenze con parentesi tonde "()" o parentesi quadre "[]".
   • Creazione del diagramma: Disegna un diagramma dell'automa a stati finiti. Gli stati dovrebbero rappresentare il progresso nella lettura della sequenza di parentesi. Le transizioni di stato dovrebbero essere basate sulle parentesi lette dall'input.
   • Definizione delle regole: Scrivi le regole per le transizioni di stato. Ad esempio, quando leggi "(", vai a uno stato in cui aspetti il corrispondente ")". Se incontri una parentesi chiusa quando non aspetti, vai a uno stato di errore.
   • Test dell'automa: Utilizza diverse sequenze di parentesi come input per verificare che l'automa riconosca correttamente le sequenze bilanciate.

Esercizio 4: Riconoscimento di Parole Palindrome

1. Obiettivo: L'obiettivo di questo esercizio è creare un automa a stati finiti che riconosca parole palindrome. Le parole palindrome sono quelle che si leggono allo stesso modo da sinistra a destra e da destra a sinistra, come "radar" o "anna."

2. Istruzioni dettagliate:

   • Creazione del diagramma: Disegna un diagramma dell'automa a stati finiti. Gli stati dovrebbero rappresentare il progresso nella lettura della parola. Le transizioni di stato dovrebbero essere basate sulle lettere lette dall'input.
   • Definizione delle regole: Scrivi le regole per le transizioni di stato. Ad esempio, quando leggi una lettera, sposta l'automa a uno stato successivo e memorizza la lettera. Se incontri una lettera diversa da quella memorizzata, vai a uno stato di errore.
   • Stato di accettazione: Aggiungi uno stato di accettazione in cui l'automa riconosce che la parola è una parola palindroma.
   • Test dell'automa: Utilizza diverse parole, alcune palindrome e altre no, come input per verificare che l'automa riconosca correttamente le parole palindrome.

Esercizio 5: Riconoscimento di Sequenze di Colori

1. Obiettivo: L'obiettivo di questo esercizio è creare un automa a stati finiti che riconosca sequenze di colori. Supponiamo che tu voglia riconoscere sequenze di colori come "Rosso, Verde, Blu, Rosso" o "Blu, Verde, Verde."

2. Istruzioni dettagliate:

   • Creazione del diagramma: Disegna un diagramma dell'automa a stati finiti. Gli stati dovrebbero rappresentare il progresso nella lettura dei colori. Le transizioni di stato dovrebbero essere basate sui colori letti dall'input.
   • Definizione delle regole: Scrivi le regole per le transizioni di stato. Ad esempio, quando leggi un colore, sposta l'automa a uno stato successivo. Se incontri un colore diverso da quello atteso, vai a uno stato di errore.
   • Stato di accettazione: Aggiungi uno stato di accettazione in cui l'automa riconosce che la sequenza è valida.
   • Test dell'automa: Utilizza diverse sequenze di colori, alcune valide e altre no, come input per verificare che l'automa riconosca correttamente le sequenze valide.