API 2020 07 15

Page 1

Algoritmi e Principi dell’Informatica Soluzioni al T ema d’esame 15 Luglio 2020 1 Informatica teorica Esercizio 1 a) Scrivere una grammatica a potenza generativa minima che generi il linguaggio L1 di tutte le stringhe, sull’alfabeto A ={0, 1}, aventi la seguente propriet` a: la stringa ` e non vuota e, se letta da sinistra a destra, ` e il complemento della stringa letta da destra a sinistra. Per complemento di una stringa si intende la stringa ottenuta scambiando gli 0 con gli 1. b) Scrivere una grammatica a potenza generativa minima che generi il linguaggio L2 di tutte le stringhe, sull’alfabeto A ={0, 1}, che non sono palindrome. Una stringa ` e palindroma se non cambia leggendola da sinistra a destra e da destra a sinistra. c) Con riferimento alle propriet` a di chiusura dei vari tipi di linguaggi rispetto alle operazioni insiemistiche, stabilire di che tipo ` e la grammatica a potenza generativa minima che genera l’intersezione di L1 e L2. Soluzione a) Per L1: S→ 0S1| 1S0| 01| 10 b) Per L2: S→ 1X0| 0X1| 0S0| 1S1 X→ 1X| 0X| ϵ c) L’intersezione tra L1 e L2 ` e ancoraL1 (nessuna stringa di L1 ` e palindroma), quindi basta una grammatica non contestuale. Naturalmente questo ` e compatibile con il fatto che non ci sia chiusura rispetto all’intersezione tra linguaggi contestuali, il che indica semplicemente che esistono due linguaggi NC la cui intersezione non ` e NC, ma non vuol dire che l’intersezione di due linguaggi NC non possa essere NC. Esercizio 2 a) Data una generica macchina di Turing non deterministicaM e una generica stringax, ` e decidibile stabilire se esistono almeno due cammini distinti di computazione effettuati da M che portano all’accettazione della stringa x? b) Il problema ` e semidecidibile? c) Come cambiano le risposte alle domande precedenti se M…