Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Import quality: text was extracted directly from the original document.
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
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…
First page of the document.
