API 2022 02 08

Page 1

Algoritmi e Principi dell’Informatica Soluzioni al Tema d’esame 8 febbraio 2022 Informatica teorica Esercizio 1 (8 punti) Si consideri il linguaggio sull’alfabeto Σ = {a,b,c,d } composto da tutte e sole le stringhe in cui: 1. compare al pi` u una sola c o una sola d, mai entrambe, 2. se compare una c, il numero di a a sinistra della c ` e uguale a quello dib a sinistra della c; idem a destra della c; 3. se compare una d, il numero di a a sinistra della d ` e uguale al doppio di quello delleb a sinistra della d; idem a destra della d; 4. Nel caso in cui non compaiano c o d, il numero di a e b ` e arbitrario. Si fornisca una grammatica a potenza minima che genera il linguaggio descritto. Soluzione Una grammatica a potenza minima (libera dal contesto) che genera il linguaggio ` e la seguente: S→A|B|C A→aA|bA|ε B→B′cB′ B′→aB′bB′|bB′aB′|ε C→C′dC′ C′→aC′aC′bC′|aC′bC′aC′|bC′aC′aC′|ε Esercizio 2 (8 punti) Uno statoq di una macchina di TuringM viene detto utile se esiste una stringaw tale per cuiq viene raggiunto durante l’esecuzione diM quandow si trova in ingresso, ovvero, dettoq0 lo stato iniziale diM,q ` e utile se∃w,x,y,α 1,...α k,β 1,...,β k⟨q0,↑w,↑Z0,..., ↑Z0⟩⊢∗ M⟨q,x↑y,α 1↑β1,...,α k↑βk⟩, con x·y =w. 1. `E decidibile stabilire, data una macchina di Turing M e un suo stato q, se q sia utile? 2. `E semidecidibile il problema di cui sopra? Soluzione 1. Il problema ` e indecidibile. Se fosse decidibile potremmo infatti decidere anche il problema della emptiness (cio` e il problema di stabilire se il linguaggio accettato ` e vuoto) per una generica macchina M; la emptiness ` e notoriamente indecidibile (e se ne pu` o ricavare immediatamente l’indecidibilit` a anche mediante il teorema di Rice). Infatti, basterebbe decidere se lo stato finale diM ` e utile (o almeno uno degli…