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. |
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,
|
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 |
24
|
Scarto mattoni |
25
|
SISTEMA DI APERTURA
E CHIUSURA DI DUE PORTE
|
26
|
SOMMA NUMERI BINARI
|
27
|
APERTURA/CHIUSURA
CANCELLO AUTOMATICO
|
28
|
MOTORE ELETTRICO
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È 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):
Questi ingressi
potranno essere immediati, vale a dire bottoni che fanno avanzare
automaticamen-te l'automa.
|
30
|
DISTRIBUTORE CAFFÈ
E CAPPUCCINO 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):
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:
|
31
|
DISTRIBUTORE CAFFÈ
E CAPPUCCINO 2 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):
Questi ingressi potranno essere immediati, vale a dire bottoni che fanno avanzare automaticamen-te l'automa. Dovremo poi prevedere le seguenti uscite:
|
32
|
RICONOSCITORE ABBC
E BCA, CON CONCATENAZIONE
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
|
34
|
PARITÀ E DISPARITÀ
DEGLI O E DEGLI 1
Esempio: ------------ seq. valida ----------------
Uscita
--------------------------------- p1 d0 |
35
|
TELECOMANDO
TELEVISORE
|
36
|
TELEVISORE
TELECOMANDO 2 |
37
|
REGOLAZIONE
INGRESSI BANCA
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 |
38
|
RICONOSCITORE
NUMERI FLOATING POINT, SECONDO LA SINTASSI C 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:
|
42
|
AUTOMI
DETERMINISTICI SULL’ALFABETO E={a,b}
|
43
|
AUTOMI
DETERMINISTICI SULL’ALFABETO E={a,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}
|
46
|
UOMO, CAPRA,
LUPO, CAVOLO
Gli eventi saranno:
Una volta costruito l’automa:
|
47 |
TRE MISSIONARI E
TRE CANNIBALI
|