API 2022 01 20

Page 1

Algoritmi e Principi dell’Informatica T ema d’esame del 20 Gennaio 2022 Esercizio 1 (8 punti). Si consideri la seguente grammatica: G =    S → CBS|CS|BS|a CB → BC CC → c BB → b a) Che tipo di grammatica ` e G? b) Che linguaggio genera G? c) Si scriva un automa a potenza minima che accetti il linguaggio generato da G. Soluzione a) La grammatica ` e di tipo non ristretto. b) Il linguaggio generato da G ` e regolare; in particolare ` e quello rappresentato dall’espressione regolare (b|c)∗a. c) L’automa a potenza minima che riconosce L(G) ` e il seguente automa a stati finiti: q0 q1 a b,c Esercizio 2 (8 punti). Si consideri una macchina di Turing universale M fissata, a nastro singolo. Sia Σ l’alfabeto del nastro di M. a) `E calcolabile la funzione f : { 1 se M(s)̸=⊥ 0 se M(s) =⊥ che riceve in ingresso una qualunque stringa s∈ ⋃100 i=0 Σi? b) `E calcolabile la funzione g : { 1 se M(s)̸=⊥ ⊥ se M(s) =⊥ che riceve in ingresso una qualunque stringa s∈ ⋃ i=2k,k∈N Σi? Soluzione 1/3 a) S` ı. Il dominio della funzione da calcolare ` e finito, quindi essa ` e rappresentabile da una ta- bella di dimensioni finite, contenente la corrispondenza ingresso-uscita tra la stringa s ed il comportamento della macchina M quando s viene data in ingresso. b) S` ı, in particolare g pu` o essere calcolata emulando M(s) sino alla sua eventuale terminazione. Se M(s) termina, allora g restituisce 1, risultando cos` ı conforme al comportamento richiesto. Esercizio 3 (8 punti) Si consideri un vettore di n interi. Si descriva in pseudocodice la procedura che ordina il vettore in ordine crescente in base al valore del resto della divisione di ognuno degli elementi per 4. Elementi con lo stesso valore di resto della divisione possono trovarsi in qualunque ordine tra loro. Il vettore ordinato avr`…