API 2018 04 27

Page 1

Algoritmi e Principi dell'Informatica Prima Prova in Itinere (modulo Informatica teorica) 27 Aprile 2018 Il tempo a disposizione è di 1 ora e 30 minuti. Esercizio 1 (Punti 6/15) a. Si progetti un automa o una grammatica (solo uno dei due!) a potenza minima che riconosca/generi il linguaggio L1 = { (12n02n1n0n)m | n=1, m>0 }. b. Si consideri ora il linguaggio L2 = { (12n02n1n0n)m | n>0, m>0 }, che comprende, ad esempio, le stringhe 110010, 110010110010 e 111100001100111100001100, mentre non comprende le stringhe 101011001100, 110010111100001100 e 11110000110011001010. Si indichi, motivando opportunamente la risposta, la classe di automi/grammatiche a potenza minima che riconosca/generi L2. Non serve fornire l’automa o la grammatica. Esercizio 2 (Punti 6/15) Si consideri un segnale su tempo continuo ad onde quadre "semiperiodico" a valore 0 o 1. Per semiperiodico si intende che esso alterna onde di durata T ad onde di durata T/2. Più precisamente, la forma del segnale è esemplificata nella figura 1 sottostante. Figura 1: segnale a forma quadra a periodo T (per onde dispari) o T/2 (per onde pari). Le onde dispari hanno durata T, in cui la prima semionda, di durata T/2, vale 1 e la seconda 0. Le onde pari hanno periodo T/2 e sono anch'esse divise in due semionde di uguale durata T/4. Si specifichi il comportamento del segnale così descritto mediante una formula logica del prim'ordine. Sono consentiti i seguenti simboli, da non specificare ulteriormente: • la funzione S(t), che restituisce il valore del segnale (0 o 1) al tempo t; • il predicato int(n), che specifica che il valore della variabile n è un intero non negativo; • la costante T; • costanti intere (0, 1, …), operazioni aritmetiche (+, -, ⋅, /) e comparatori (<, =, £, …). Esercizio 3 (punti 6/15) 1. Si consideri…