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 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…
First page of the document.
