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 Prima Prova in Itinere 25 Novembre 2014 Il tempo a disposizione è di 1 ora e 45 minuti. Esercizio 1 (punti 6/15 senza la parte facoltativa, 9 con la parte facoltativa) Si ricordi che la stringa inversa di una generica stringa w, qui denotata wR, è ottenuta da w scrivendo i suoi caratteri in ordine inverso, ad esempio abaabbR = bbaaba, aaabbbR = bbbaaa. L’operazione di inversione viene estesa dalle stringhe ai linguaggi nel modo naturale: LR = {wR | w ∈L } Si dica, con brevi spiegazioni, quali delle seguenti famiglie di linguaggi sono chiuse rispetto all’operazione di inversione: • Il linguaggi regolari • I linguaggi non contestuali • I linguaggi generati da grammatiche non ristrette • (Parte facoltativa) I linguaggi non contestuali deterministici NB: la parte facoltativa verrà valutata solo se nelle restanti parti si saranno ottenuti almeno 5 punti. Esercizio 2 (punti 7/15) Due macchine di Turing (MT) si dicono isomorfe se: • hanno lo stesso numero di nastri; • ad ogni mossa spostano le rispettive testine del nastro i-esimo alla stessa maniera (entrambe a destra o entrambe a sinistra o lasciano entrambe ferme); Si noti che di conseguenza due MT isomorfe usano esattamente le stesse celle di memoria. E' decidibile il fatto che due qualsiasi MT isomorfe siano equivalenti, ossia calcolino la stessa funzione o riconoscano lo stesso linguaggio? Giustificare brevemente la risposta Esercizio 3 (punti 5/15) Specificare in logica del prim’ordine il linguaggio L1 = { anbncn | n≥0 }. Nella specifica si possono usare esclusivamente i seguenti predicati e funzioni: • il predicato di appartenenza insiemistica ∈ • il predicato di uguaglianza = • la funzione di concatenazione ⋅ • le costanti dei caratteri alfabetici a, b, c e la stringa vuota ε •…
First page of the document.
