API 2021 06 29

Pagina 1

Algoritmi e Principi dell’Informatica T ema d’esame del 29 Giugno 2021 1 Informatica teorica Esercizio 1 (8 punti) a) Scrivere una grammatica a potenza minima che generi il linguaggio seguente: L1 = {(bc)m | m ≥ 2} b) Sfruttando la risposta al punto precedente, scrivere una grammatica a potenza minima che generi il linguaggio seguente: L2 = {bkaℓ(bc)manbp | k > p, 2ℓ = n, m ≥ 2} Soluzione a) `E sufficiente una grammatica regolare, dove S0 ` e l’assioma. S0 → bS1 S1 → cS2 S2 → bS3 S3 → c | cS2 b) `E sufficiente una grammatica non contestuale. Il linguaggio pu` o infatti anche essere pensato nel modo seguente: L2 = {bsbpaℓ(bc)m(aa)ℓbp | s ≥ 1, p ≥ 0, ℓ ≥ 0, m ≥ 2} S → U V U → bU | b 1 o pi` ub V → bV b | W generiamo p lettere b da ambo i lati W → aW aa | S0 generiamo ℓ lettere a a sx e 2 ℓ a dx dove S0 ` e il simbolo iniziale della grammatica perL1. Esercizio 2 (8 punti) Sia L1 un linguaggio ricorsivamente enumerabile, L2 un linguaggio regolare e L = L1 ∩ L2 la loro intersezione. Per ciascuna delle seguenti classi di linguaggi, si argomenti se L pu` o farne parte, deve necessariamente farne parte o non pu` o farne parte: a) linguaggi regolari; b) linguaggi ricorsivi; c) linguaggi ricorsivamente enumerabili. Motivare opportunamente e fornire esempi laddove appropriato. Soluzione 1/3 a) Pu` o farne parte: seL1 ` e regolare allora ancheL ` e regolare (chiusura rispetto a intersezione); ad esempio, se L1 = ∅ abbiamo L = ∅. Pu` o non farne parte: seL1 non ` e regolare eL2 = A∗, dove A ` e l’alfabeto, alloraL non ` e regolare. b) In modo simile al punto precedente, se L1 ` e ricorsivo allora ancheL ` e ricorsivo (chiusura rispetto a intersezione), altrimenti potrebbe non esserlo. La ragione ` e che L2, essendo regolare, ` e anche ricorsivo. c) L ` e certamente ricorsivamente…