Computer Engineering - Algoritmi e Principi dell'Informatica

Full exam

Algoritmi e Principi dell’Informatica Appello del 1 Settembre 2016 Esercizio 1 (9 punti) 1. Si costruisca un automa, preferibilmente a minima potenza riconoscitiva, che accetti il linguaggio L1 ⊆ {a,b}* costituito da tutte e sole le stringhe w tali che, se w contiene la sottostringa aa, allora la sua lunghezza è dispari. 2. Si determini la famiglia di automi a potenza riconoscitiva minima -o minimale- tale che un suo membro riconosca il linguaggio L2 ⊆ {a,b,c}*, costituito da tutte e sole le stringhe w tali che w includa la stringa canc (per qualche n > 0) e, successivamente, la stringa ba2nb (la stringa w può contenere altre sottostringhe oltre alle suddette canc e ba2nb). a. Si costruisca un automa in tale famiglia che riconosca L2; b. Si costruisca una grammatica, preferibilmente a minima potenza generativa, che generi L2. Esercizio 2 (8 punti) Per entrambi i punti seguenti si assuma che L sia un linguaggio infinito costruito su un alfabeto A. 1. Sia L un linguaggio ricorsivo. Esiste necessariamente una enumerazione algoritmica E che enumera tutte le stringhe di L in ordine lessicografico? Motivare brevemente la risposta. 2. Sia E una enumerazione algoritmica E che enumera tutte le stringhe di un linguaggio L in ordine lessicografico. L è necessariamente ricorsivo? Motivare brevemente la risposta. Tracce delle soluzioni Esercizio 1 1. Il seguente automa a stati finiti riconosce L1. 2. Un automa a stati finiti non è evidentemente in grado di riconoscere L2 a causa della necessità di un conteggio illimitato. Neanche un automa a pila deterministico è in grado di operare il riconoscimento perché una stringa del linguaggio può contenere diverse bbabaaa,ba,bab sottostringhe del tipo canc, di cui solo una abbia una corrispondente sottostringa ba2nb come ad esempio nella stringa acaaacbbcaccbaabc. E’ anche possibile costruire una rete di Petri che riconosca L2; quindi, siccome PDA e reti di Petri hanno potenza riconoscitiva incomparabile, vi sono almeno due famiglie di automi, tra quelle classiche, a potenza riconoscitiva minimale, in grado di formalizzare L2. a. b. S → XDX D → caEaab E → aEaa | cXb X → aX | bX | cX | ε Esercizio 2 1) L è ricorsivo, quindi esiste un “decisore” per L, cioè una macchina di Turing M che termina sempre e scrive 1 in uscita se la stringa in ingresso appartiene a L, 0 altrimenti. L’enumerazione algoritmica E richiesta si ottiene come segue: basta enumerare tutte le stringhe di A* in ordine lessicografico (cosa sempre possibile) e, per ciascuna di esse, testarne l’appartenenza ad L tramite M (che è disponibile per ipotesi), stampandola in uscita solo se appartiene a L. 2) L è enumerabile algoritmicamente mediante E in ordine lessicografico. Si può quindi costruire un decider M per L come segue: quando riceve una stringa x in ingresso, M esegue l’enumerazione E e legge la lista di tutte le stringhe di L in ordine lessicografico fino a che non compare una stringa che lessicograficamente stia dopo x (tale stringa deve necessariamente esistere, perché L è infinito). Se x è apparso nell’enumerazione, allora M stampa 1 in uscita, altrimenti stampa 0. a,Z 0/Z 0 b,Z 0/Z 0 c,Z 0/Z 0 c,Z 0/Z 0 a,Z 0/Z 0AA a,A/AAAc,A/A a,A/A b,A/A c,A/A b,A/Ab,Z 0/Z 0 a,Z 0/Z 0 b,Z 0/Z 0 c,Z 0/Z 0 a,A/ ε