API 2016 09 001

Pagina 1

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 b b a b a a a,b a,b a b sottostringhe del tipo canc, di cui solo una abbia una corrispondente sottostringa ba2nb come ad esempio…