Sequenza Selezione Iterazione Funzioni Ricorsione Operat. su interi Stringhe Vettori Array
Tabelle File Liste Alberi Esami Maturità Preparazione esami Database Macchina di Turing Automi
Algebra Geometria Giochi            

Esercizi sugli Automi

1

Progettare un automa che emette in uscita un biglietto dopo che sono state inserite due monete da 0,2€. L'automa funziona solo con monete da 0,2€.

2

Progettare un automa che emette un biglietto dopo che sono stati inseriti 0,60€. L'automa funziona con monete da 10 o da 20 centesimi di Euro e non fornisce resto.

3

Progettare un automa che emette un biglietto dopo che sono stati inseriti 0,60€. L'automa funziona con monete da  10 o da 20 centesimi di Euro e fornisce resto a richiesta.

4

Progettare un automa a stati finiti che realizzi un distributore automatico di francobolli, che accetti monete da 50, 20 e 10 centesimi di Euro. Il prezzo del francobollo è di Euro 0,80 ed il distributore può dare un resto max di 20 centesimi.

5

Progettare un automa che distribuisce lattine di un solo tipo dopo che sono state introdotte due monete di un unico valore. Se il distributore è spento si "mangia" la moneta eventualmente introdotta.

6

L'automa è un distributore di bevande che distribuisce due tipi di bevande emettendo una lattina dopo che sono state introdotte due monete da L. 20 centesimi di Euro ed è stato scelto il tipo di bevanda. L'automa non restituisce monete.

7

L'automa è ancora un distributore di bevande come il precedente. In questo caso però vengono restituite delle monete a richiesta o anche nel caso sia stata introdotta una moneta in eccedenza.

8

Progettare un automa, distributore di bevande, che distribuisce due tipi di bevande (Coca Cola, Fanta), emettendo una lattina dopo che sono stati introdotti 40 centesimi di Euro ed é stato scelto il tipo di bevanda. L'automa accetta monete da 10c e 20c di Euro e non restituisce monete.

9

Progettare un automa, distributore di bevande calde, che distribuisce tre tipi di bevande calde e fornisce o no, a richiesta dell'utente, lo zucchero. Ogni bevanda costa 50c di Euro e l'automa accetta monete da 10c e 20c.

10

Progettare un automa che fornisce monete da 50c € in cambio di monete da 10c e da 20c di Euro. L'automa non fornisce in alcun modo resto.

11

L'automa è un sistema di regolazione di un orologio digitale. L'orologio è munito di tre pulsanti la cui pressione chiameremo P1, P2, P3 che servono per la regolazione delle ore, minuti, mese, giorno e per il passaggio dalla modalità del display in cui vengono mostrati ore e minuti alla modalità in cui vengono mostrati mese e giorno. Il tasto P1 serve per passare dallo stato in cui il display mostra ore-minuti agli stati di regolazione, il tasto P2 serve per incrementare il valore at-tualmente presente sul display (inc=incrementa), il tasto P3 è un tasto bistabile tra le modalità del display ore-minuti e mese-giorno.

12

Abbiamo una macchina che riceve sequenzialmente ma disordinatamente rondelle, viti, dadi. La macchina deve ordinare la successione secondo la sequenza vite-rondella-dado. I pezzi non i ordine devono essere scartati dalla macchina.

13

L'automa riceve in ingresso sequenze di 0 (zero) ed 1 e deve "riconoscere", producendo un segnale di OK , le sequenze 010 , senza concatenazione. Questo significa che , ad esempio la sequenza 01010 produce un solo OK mentre, con la concatenazione, la sequenza 01010 produce due OK.
L'automa è costruito come automa di Mealy (automa improprio).

14

L'automa riceve in ingresso sequenze di 0 (zero) ed 1 e deve "riconoscere" , producendo un segnale di OK , le sequenze 010 , senza concatenazione. Questo significa che , ad esempio

  mentre, con la concatenazione,



L'automa è costruito come automa di Mealy (automa improprio).
 

15

L'automa riceve in ingresso sequenze di 0 (zero) ed 1 e deve "riconoscere" , producendo un segnale di OK , le sequenze 010 , con concatenazione. L'automa è stavolta un automa di Moore (automa proprio).
 

16

L'automa riceve in ingresso stringhe di 0 (zero) ed 1 e deve riconoscere, tornando allo stato iniziale ed emettendo un segnale di OK appena è rilevata la situazione richiesta, le stringhe costituite da un numero pari di 0 e un numero pari di 1.
 

17

Automa riconoscitore della sequenza ABA senza concatenazione. L'automa emette un segnale SI ogni volta che viene individuata la sequenza.
 

18

L'automa riceve in ingresso stringhe di A e di B e riconosce le sequenze ABA con concatenazione.

19

Automa riconoscitore di sequenza AABB.

20

L'automa riceve in ingresso una sequenza di caratteri alfabetici e segnala con un SI la ricezione della sequenza END.

21

L'automa controlla la correttezza della successione delle parentesi in una espressione algebrica senza preoccuparsi di tutti gli altri caratteri che vengono immessi nell'espressione. L'automa controlla espressioni con, al massimo, due livelli di parentesi. E' importante osservare che automi di questo genere sono a stati finiti purché finito sia il numero dei livelli di parentesi.

22

Progettare un automa che riconosce la correttezza sintattica di una stringa, terminata dal carattere *, contenente una successione di parentesi (tonde e quadre), conforme alle regole dell’algebra (deve verificare il bilanciamento e la corretta successione delle parentesi – es. )(* non accettata – ([])* non accettata – [()()]* accettata).

23

ASCENSORE A DUE PIANI
Vogliamo qui descrivere il comportamento di un ascensore a due piani (piano terra e due piani) limitatamente a ciò che riguarda le chiamate dai pulsanti ai piani.

24

Scarto mattoni
Una fabbrica produce mattoni di 20 cm con una tolleranza del 10%. Il mattone passa su un nastro dotato di 3 fotocellule. Tra la fotocellula A e la B ci sono 20cm, mentre tra la B e la C ci sono 20 cm. Se il mattone è più lungo di 22 cm o più corto di 20 cm, l’automa da un impulso ad un braccio meccanico che scarta il mattone. Si suppone che il mattone non possa essere più corto di 2 cm e che tra un mattone e l’altro ci siano almeno 45 cm.

25

SISTEMA DI APERTURA E CHIUSURA DI DUE PORTE
L'automa è un sistema di apertura e chiusura di due porte per regolare l'accesso ad una banca. Ad ognuna delle due porte è dato un verso di percorrenza : una porta è solo per l'in-gresso e l'altra solo per l'uscita. L'apertura o chiusura delle due porte è effettuata da un motore; due semafori, uno per la porta d'ingresso e l'altro per la porta d'uscita, indicano se l'ingresso o l'u-scita sono possibili; le due porte sono dotate di un pulsante di chiamata. Il flusso è controllato dal-le seguenti regole:

  1. Le porte normalmente devono essere chiuse.

  2. Quando una delle due porte è aperta l'altra deve rimanere chiusa.

  3. Se si verifica la chiamata simultanea dalla porta d'ingresso e dalla porta d'uscita, ha la prece-denza l'ingresso.

  4. Un sensore collegato al motore informa il sistema se è in corso un'operazione di apertura o chiusura di una delle due porte.

26

SOMMA NUMERI BINARI
Vogliamo progettare un automa che, dati due numeri binari di n bit, calcoli la loro somma secondo lo schema di calcolo che si utilizza quando si fa la somma "a mano", cioè partendo dalle due cifre meno significative (quelle a destra) e, utilizzando i riporti, muovendo verso sinistra.

27

APERTURA/CHIUSURA CANCELLO AUTOMATICO
Un dispositivo di controllo permette l'apertura di un cancello automatico quando vi giunge un se-gnale del comando portatile che corrisponde ad 1 "logico", altrimenti se giunge un segnale che corrisponde ad uno 0 "logico" esso si chiude.

28

MOTORE ELETTRICO
L'avviamento di un'automobile è attuato tramite un motore elettrico comandato da un dispositivo che fornisce con uno 0 logico il consenso (0=Gira, 1=Fermo).

Lo stesso dispositivo riceve un comando dalla chiave di avviamento, che "emette" uno 0 logico quando viene girata dal guidatore, ed analizza due ulteriori segnali provenienti da una termocoppia (1=motore già acceso) e dalla leva di comando del cambio automatico (0=posizione folle N).
 

29

DISTRIBUTORE DI CAFFÈ

Scrivere l'automa di un distributore di caffè. Il caffè costa 400 Lire. Il distributore accetta mo-nete da 100, 200 e 500 Lire.

Appena viene immessa una cifra sufficiente, il distributore consegna il caffè. Nel caso siano stati inseriti più soldi del necessario, il distributore riconoscerà un credito, al quale si aggiungeranno le monete successive. Il distributore non dà resto.

È da osservare che, la cifra massima che si può inserire con le monete indicate è di 800 Lire, in-fatti se si introducono 400 Lire si ottiene un caffè che estingue il credito. Se invece si introducono 300 Lire, introducendo un'ulteriore moneta da 500 Lire si ottiene appunto il credito di 800 Lire. Se si raggiunge questo credito la macchina produce automaticamente due caffè.

L'automa avrà i seguenti ingressi (espressi in lire):

  • 100

  • 200

  • 300

Questi ingressi potranno essere immediati, vale a dire bottoni che fanno avanzare automaticamen-te l'automa.

Dovremo poi prevedere i seguenti valori per l' uscita:

  • mancano soldi

  • caffè

  • fa due caffè o fa caffè e visualizza resto

 

30

DISTRIBUTORE CAFFÈ E CAPPUCCINO
Scrivere l'automa di un distributore di caffè o cappuccino. Il caffè costa 400 Lire ed il cappuccino 600 Lire. Il distributore accetta monete da 100, 200 e 500 Lire.

mancano soldi.

Se il credito raggiunge o supera le 400 Lire, il distributore visualizza il messaggio scelta : caffè. A questo punto l'utente può inserire altre monete, per chiedere un cappuccino, oppure premere il ta-sto Caffè, per ottenere un caffè.

Se il credito raggiunge o supera le 600 Lire, il distributore visualizza il messaggio scelta : caffè o cappuccino. A questo punto l'utente può premere il tasto Caffè, per ottenere un caffè (viene visua-lizzato il messaggio fa caffè oppure fa caffè e visualizza resto, nel caso il credito sia superiore alla 400 Lire) o Cappuccino per ottenere un cappuccino (viene visualizzato il messaggio fa cappuccino oppure fa cappuccino e visualizza resto, nel caso il credito sia superiore alla 600 Lire). Se invece si inserisca altra moneta, viene visualizzato il messaggio non accetta altri soldi : effettuare la scelta e non accetta la moneta.

Nel caso siano stati inseriti più soldi del necessario, il distributore riconoscerà un credito, al quale si aggiungeranno le monete successive.

È da osservare che, la cifra massima che si può inserire con le monete indicate è di 1000 Lire, in-fatti se si introducono 600 Lire il distributore non accetta più moneta, quindi il credito non cresce più. Se invece si introducono 500 Lire, con una qualunque combinazione di monete, introducendo un'ulteriore moneta da 500 Lire si ottiene appunto il credito di 1000 Lire.

L'automa avrà i seguenti ingressi (le cifre sono espresse in lire):

  • 100

  • 200

  • 300

  • Caffè

  • Cappuccino

Questi ingressi potranno essere immediati, vale a dire bottoni che fanno avanzare automaticamen-te l'automa.

Dovremo poi prevedere i seguenti valori per l' uscita:

  • mancano soldi

  • scelta : caffè

  • scelta : caffè o cappuccino

  • fa caffè

  • fa cappuccino

  • fa caffè e visualizza resto

  • fa cappuccino e visualizza resto

  • non accetta altri soldi : effettuare la scelta

 

31

DISTRIBUTORE CAFFÈ E CAPPUCCINO 2

Scrivere l'automa di un distributore di caffè o cappuccino. Il caffè costa 400 Lire ed il cap-puccino 600 Lire. Il distributore accetta monete da 100, 200 e 500 Lire.

Il distributore possiede inoltre un display, uno sportello dal quale ritirare il prodotto ed uno sportel-lino nel quale verranno lasciate le monete rifiutate.

Se il credito non raggiunge le 400 Lire il distributore visualizza il messaggio mancano soldi sul display.

Se il credito raggiunge o supera le 400 Lire, il distributore visualizza il messaggio scelta : caffè sul display. A questo punto l'utente può inserire altre monete, per chiedere un cappuccino, oppure premere il tasto Caffè, per ottenere un caffè.

Se il credito raggiunge o supera le 600 Lire, il distributore visualizza il messaggio scelta : caffè o cappuccino sul display. A questo punto l'utente può premere il tasto Caffè, per ottenere un caffè (lo sportello del prodotto indicherà il fatto, ad esempio con il messaggio ritira il caffè) o Cappucci-no per ottenere un cappuccino (lo sportello del prodotto indicherà il fatto, ad esempio con il mes-saggio ritira il cappuccino). Se invece si inserisca altra moneta, questa viene rifiutata, inviandola allo sportellino per le monete rifiutate.

Nel caso siano stati inseriti più soldi del necessario, il distributore riconoscerà un credito, al quale si aggiungeranno le monete successive.

È da osservare che, la cifra massima che si può inserire con le monete indicate è di 1000 Lire, in-fatti se si introducono 600 Lire il distributore non accetta più moneta, quindi il credito non cresce più. Se invece si introducono 500 Lire, con una qualunque combinazione di monete, introducendo un'ulteriore moneta da 500 Lire si ottiene appunto il credito di 1000 Lire.

L'automa avrà i seguenti ingressi (le cifre sono espresse in lire):

  • 100

  • 200

  • 300

  • Caffè

  • Cappuccino

Questi ingressi potranno essere immediati, vale a dire bottoni che fanno avanzare automaticamen-te l'automa.

Dovremo poi prevedere le seguenti uscite:

  • Display con i seguenti valori:

    • mancano soldi

    • scelta : caffè

    • scelta : caffè o cappuccino

    • non accetta altri soldi : effettuare la scelta

  • Sportello del Prodotto con i seguenti valori:

    • ritira il caffè

    • ritira il cappuccino

    • Stringa vuota per indicare nessun contenuto

  • Sportellino per le Monete Rifiutate con i seguenti valori:

    • restituisce la moneta immessa

    • Stringa vuota per indicare nessun contenuto

32

RICONOSCITORE ABBC E BCA, CON CONCATENAZIONE
Scrivere un automa riconoscitore in grado di riconoscere, in una sequenza continua di simboli scelti tra a, b e c, ogni occorrenza di una o dell'altra delle stringhe abbc o bca. Le sequenza deve esse-re riconosciute anche se sono sovrapposte una all'altra (notare che il termine di una sequenza po-trebbe anche essere l'inizio dell'altra).

L'automa lavorerà sull'alfabeto { a , b , c }. L'unica uscita dell'automa assumerà il valore ricono-sciuto ABBC quando viene analizzato l'ultimo simbolo della stringa abbc e riconosciuto BCA quando viene analizzato l'ultimo simbolo della stringa bca.
 

33

INCREMENTO DI DUE
Progettare l’automa a stati finiti che effettui l’incremento di due di una stringa di quattro bit, con l’indicazione del riporto. Per tale automa vanno specificati gli insiemi degli ingressi, stati, uscite ed il diagramma degli stati.
 

34

PARITÀ E DISPARITÀ DEGLI O E DEGLI 1
Progettare un automa che riceva in ingresso {*,0,1}. Ogni sequenza significativa di 0 ed 1 cominci con un * e termini con un altro *. Le sequenze che non sono precedute e seguite da un * vengano ignorate. L'automa riporti in uscita la parità e la disparità sia degli 0 che degli 1 relativamente alle sequenze valide.

Esempio:
Ingresso 1101001*01000111011*0001001001

------------ seq. valida ----------------

Uscita --------------------------------- p1 d0
 

35

TELECOMANDO TELEVISORE
Un televisore a tre soli canali A,B,C viene pilotato da un telecomando "primordiale" composto da due soli pulsanti:

  • un pulsante ON/OFF

  • un pulsante che quando viene schiacciato fa passare dal canale corrente a quello successivo (nb: il successivo di C è A) quando si accende il televisore trasmette il canale A

36

TELEVISORE TELECOMANDO 2
Come sopra, ma con un terzo pulsante che consente di andare dal canale corrente a quello prece-dente (nb. il precedente di A è C)
 

37

REGOLAZIONE INGRESSI BANCA
All'ingresso di una banca c'è una macchina di controllo e programmazione ingressi ogni utente che arriva schiaccia un pulsante: se nella banca vi sono meno di 5 clienti, allora un display indica "EN-TRA" e la porta si apre automaticamente; se nella banca vi sono 5 clienti, il display

indica "ATTENDERE PREGO" e la porta resta chiusa ogni cliente che esce dalla banca schiaccia un pulsante e la porta di uscita si apre automaticamente

NB. La porta di uscita e quella di ingresso sono diverse.
Non considerare il caso che vi possano essere un cliente in uscita ed un cliente in in-gresso che schiacciano il rispettivo pulsante contemporaneamente e dare per assunto che le due porte non saranno mai contemporaneamente aperte.
 

38

RICONOSCITORE NUMERI FLOATING POINT, SECONDO LA SINTASSI C

Si costruisca l'automa a stati finiti corrispondente ad un riconoscitore di numeri floating point espressi secondo la sintassi C. I numeri passati all'automa sono compresi tra due delimitatori '#'. (es. #3.14#, #0.5#, #2.1e3#).

L'automa deve segnalare alla fine se il numero è scritto correttamente.

Si ignori il problema di avere degli zeri iniziali.
 

39

PARITÀ ALL’INGRESSO DEL PARLAMENTO

Vi è stato richiesto di progettare il sistema di controllo e gestione della parità all'ingresso del Parlamento Italiano. Il funzionamento deve essere il seguente: fatta l'ipotesi che all'ingresso si pre-sentino solo due tipi di parlamentari, di tipo D (parlamentari del centro-destra) e di tipo S (parlamentari del centro-sinistra), si considerino sequenze di S e D delimitate dal carattere '*'. Una sequenza di ingresso, ad esempio, potrebbe essere:

*SSSSDSSSDDDSSDSDSSSDSDSSDSDDDS*

Progettare un automa che accetti in ingresso questo tipo di sequenze e restituisca uscita PariS se il numero di S della sequenza è pari, uscita DispariS se esso è dispari.
 

40

SISTEMA DI ILLUMINAZIONE DI UNA STANZA

La stanza in esame è formata da un ingresso (definito stanza1) e da due zone laterali distinte de-nominate stanza2 (quella di sinistra) e stanza3 quella di destra. Per una corretta illuminazione so-no previste 3 lampade, una per la zona comune dell’ingresso (L1), una per il lato sinistro (L2) e una per il lato destro (L3).

L’accensione dei 3 punti luce è regolata da due pulsanti P1 e P2 posti ai lati dell’unica porta di ac-cesso, in base ai seguenti criteri:

1. Entrando nella stanza per la prima volta e premendo un pulsante, sia esso P1 o P2, si ac-cende la lampada L1 dell’ingresso.

2. Premendo ulteriormente un pulsante, la lampada L1 si spegne e si accende una delle lam-pade rimanenti:L2 se si è premuto il pulsante P1, L3 se si è premuto il pulsante P2.

3. La pressione ulteriore di uno qualsiasi dei pulsanti indica che si sta uscendo dalla stanza e spegnerà la luce accesa, qualunque essa sia.

Condizioni di funzionamento

I pulsanti P1 e P2 non possono essere premuti contemporaneamente.

Le lampade possono essere accese una alla volta, cioè non possono mai essere accese più di una lampada per volta.

 

41

GIOCO DELL’UNO, DUE O TRE

Al gioco dell'"uno, due o tre" partecipano due giocatori che a turno prelevano dal tavolo una, due o tre palline. Il numero di palline presenti all'inizio della partita può essere qual-siasi. Vince chi riesce a lasciare sul tavolo una sola pallina.

Visto il successo dei videogiochi, la tua software house ha deciso di produrre e vendere su dischetto il gioco dell'"uno, due o tre". I requisiti del prodotto sono i seguenti:

  1. all'inizio della partita ci sono 25 palline sul tavolo.

  2. il giocatore fa la prima mossa battendo 1, 2 o 3 sulla tastiera; il calcolatore preleva, a sua volta, 1, 2 o 3 palline, seguendo una sua strategia: il risultato è un certo numero di pal-line sul tavolo. Si continua così sino al termine della partita.

  3. se il giocatore compie una mossa illecita (ad esempio, battendo 2 o 3 quando ci sono solo 2 palline sul tavolo), la vittoria viene automaticamente assegnata alla macchina.

  4. la strategia seguita dal calcolatore offre al giocatore la possibilità di vincere la partita decidendo, ad ogni mossa, unicamente sulla base del numero di palline presenti.

  5. tra tutte le strategie che soddisfano il precedente requisito, il calcolatore sceglie quella che massimizza le sue probabilità di vittoria.

  6. il programma che realizza il gioco deve essere il più compatto possibile.

 

42

AUTOMI DETERMINISTICI SULL’ALFABETO E={a,b}

Costruire gli automi finiti deterministici sull'alfabeto E={a,b} che accettano i seguenti linguaggi:

  1. P: insieme delle parole che iniziano per ab e terminano per ba.

  2. Q: insieme delle parole che contengono almeno una a e almeno una b.

  3. R: insieme delle parole in cui ogni sottostringa aa è immediatamente seguita da almeno una b.

  4.  S: insieme delle parole palindrome di lunghezza 2.

  5. T: insieme delle parole palindrome di lunghezza 4.

  6. U: insieme delle parole palindrome.

43

AUTOMI DETERMINISTICI SULL’ALFABETO E={a,b}

Costruire gli automi finiti deterministici sull'alfabeto E={a,b} che accettano i seguenti linguaggi:

  1. R: insieme delle parole che terminano per abb;

  2. S: insieme delle parole che contengono esattamente due b;

  3. T: insieme delle parole in cui ogni a è immediatamente seguita da almeno due b;

  4. U: insieme delle parole che contengono un numero di a pari al numero b.

44

AUTOMI STRINGHE NELL’ALFABETO {0,1,2, “,”}

Disegnare il grafo dell’automa che riconosce le stringhe nell’alfabeto (0,1,2, “,”) che rappresentano in un sistema di numerazione ternario numeri interi e numeri decimali, privi entrambi di zeri in te-sta non significativi, e numeri decimali, privi di zeri in coda nella parte decimale rifiutando numeri decimali con parte decimale vuota.

(accetti, ad esempio: “1200” “2,01” e “0,0021” ma rifiuti le stringhe “00” “012” “2,0” “0,”). Si consiglia di verificare l’accettazione e il rifiuto degli esempi.
 

45

AUTOMI STRINGHE NELL’ALFABETO {a, b, c}

Sia L il linguaggio nell’alfabeto {a, b, c} costituito da tutte le stringhe che contengono la sotto-stringa aba.

  1. Progettare un automa indeterministico M che riconosce L (si noti che M ha 4 stati).

  2. seguendo la procedura generale ricavare l’automa deterministico che accetta L.

 

46

UOMO, CAPRA, LUPO, CAVOLO

Costruire un automa finito deterministico che rappresenta il seguente problema. Un uomo deve traghettare dalla sponda sinistra alla sponda destra di un fiume tre passeggeri: una capra, un lupo e un cavolo. L’uomo ha a disposizione una barca che gli consente di portare dall’altra parte un solo passeggero alla volta. Inoltre, egli non deve lasciare incustoditi sulla stessa sponda del fiume: (a) la capra con il cavolo; (b) il lupo con la capra.

Per la costruzione dell’automa etichettare i vari stati con la seguente notazione:

  • (C L V U) : Capra, Lupo, caVolo, Uomo sulla sponda sinistra;

  • (C L V U) : Capra, Lupo, caVolo sulla sponda sinistra; Uomo sulla sponda destra;

  • ecc.

Gli eventi saranno:

  • u: l’uomo compie la traversata da solo;

  • uc: l’uomo compie la traversata con la capra;

  • ul: l’uomo compie la traversata con il lupo;

  • uv: l’uomo compie la traversata con il cavolo.

Una volta costruito l’automa:

  • indicare lo stato finale (uomo e passeggeri sulla sponda destra);

  • indicare gli stati proibiti (capra-cavolo oppure lupo-capra incustoditi);

  • determinare se esiste una parola accettata che possa venir generata con una produzione che non passi per alcuno stato proibito e, in caso positivo, indicare tale produzione.

 

47

TRE MISSIONARI E TRE CANNIBALI

Costruire un automa finito deterministico che rappresenti il seguente problema. Tre missionari e tre cannibali sono sulla riva destra di un fiume e devono attraversarlo. Per farlo devono utilizzare una barca che non può trasportare più di due persone alla volta. Durante i trasferimenti, se su una delle due rive i cannibali sono in numero maggiore dei missionari se li mangiano: tali stati devono essere evitati. In particolare:

  • Indicare tutti i possibili stati in cui può trovarsi questo sistema (CCCMMMB: tre cannibali, tre missionari e la barca sulla sponda destra; CCCMMMB: un cannibale, un missionario e la barca sulla sponda sinistra, due cannibali e due missionari sulla sponda destra; ecc).

  • Indicare l'alfabeto degli eventi (c: un cannibale attraversa il fiume; cc: due cannibali attraversano il fiume, ecc.).

  • Indicare lo stato iniziale e il solo stato finale.

  • Indicare gli stati proibiti .

  • Determinare se esiste una parola accettata che possa venir generata con una produzione che non passi per alcuno stato proibito e, in caso positivo, indicare tale produzione.