Fondamenti di Informatica, 29 Gennaio 2019

Non e' ammesso l'uso di alcun testo, appunti, calcolatrici, telefonini o smartphone (questi ultimi vanno riposti lontano dalla propria persona). Le risposte vanno scritte nel foglio di bella copia. Si raccomanda la massima SINTETICITA'. L'eccessiva verbosita' verra' considerata negativamente.
  • Per sostenere l'esame e' obbligatorio essersi prenotati sul portale studenti del nostro ateneo. Elaborati di studenti non prenotati NON verranno valutati.
  • I risultati verranno indicati nella pagina web del corso. Date ed orari degli orali, sul Forum.


    • PARTE I
    Esercizio 1
    (a) Fornire la definizione di Insieme delle conseguenze di un insieme di ipotesi Γ in un sistema formale D. Fornire inoltre le definizioni di Teoria e di insieme consistente di fbf.

    (a-B) Fornire la definizione di Insieme dei teoremi di un sistema formale D. Fornire inoltre le definizioni di Teoria e di insieme inconsistente di fbf.

    (b) La seguente e' una dimostrazione (non completamente specificata) di un teorema (non completamente specificato), nel sistema formale CL.
    Ricopiarla inserendo le parti mancanti. 
    1.  skk = kk(kk)  (?)
2.  ??            (axk)
3.  skk = ?       (trans)(?,?)
    dove gli assiomi e regole di CL sono: 
             -------(axk)   -------------(axs)
          kMN=M          sMNR=MR(NR)

  R=R'  MR=NR                 R=R'  RM=RN                              
---------------(cong1)    ---------------(cong2)  
   MR=NR'                       RM=R'N 

 M=N           M=N N=R
-----(symm)   ---------(trans)   ------(refl)
 N=M             M=R               M=M
    Quante dimostrazioni si possono avere di questo stesso teorema in CL? Giustificare la risposta.

    (c) Avendo a disposizione i seguenti risultati:
    Teorema Sia Γ un insieme consistente di fbf di P0, e sia α tale che Γ ⊬Po α. Allora Γ ∪ {¬α} e' consistente.
    Proposizione Sia δ una fbf di Po. Allora δ ⊢Po ¬¬δ
    Dimostrare che se Γ∪{α} e' contraddittorio allora Γ ⊢Po ¬α.
    Esercizio 2
    (a) Dare la definizione di Automa a stati finiti NON DETERMINISTICO.

    (b) Sia L il linguaggio di tutte le stringhe sull'alfabeto {a,b} che hanno il carattere 'b' in penultima posizione. Scrivere un'espressione regolare che denota il linguaggio L.
    (b-B) Sia L il linguaggio di tutte le stringhe sull'alfabeto {a,b} che hanno il carattere 'b' in seconda posizione. Scrivere un'espressione regolare che denota il linguaggio L.

    (c) Costruire un automa a stati finiti DETERMINISTICO che accetta il linguaggio L.

    PARTE II
    Esercizio 3
    (a) Fornire la definizione di Macchina Astratta e descriverne in dettaglio la componente Interprete.

    (b) Sia {{},{scontato1, pv1, alcoolico1, costapiu1}} una segnatura per la logica del primo ordine (calcolo dei predicati). Si consideri la struttura che ha come supporto l'insieme di tutti i prodotti ed in cui si interpreta Scrivere la fbf il cui valore di verita' in tale struttura coincide con quello della seguente frase in italiano
    Gli alcolici in vendita senza sconto costano tutti piu di venti euro, mentre quelli con lo sconto costano al piu venti euro.
    (a-B)
    Gli alcolici in vendita con lo sconto costano tutti al piu' venti euro, mentre quelli senza sconto costano piu' di venti euro.
    (Si hanno a disposizione entrambi i quantificatori e tutti i connettivi logici)

    (c) Fornire gli assiomi e/o le regole di inferenza che descrivono la S.O.S. del costrutto while del linguaggio WHILE.

    (c-B) Fornire gli assiomi e/o le regole di inferenza che descrivono la S.O.S. del costrutto while del linguaggio WHILE+, dove WHILE+ e' come il linguaggio WHILE con l'unica differenza che esiste un solo <test>, che e' ALL=1, che e' vero quando tutte le variabili sono uguali ad 1.

    Esercizio 4
    (a) Dare le definizioni di grammatiche di Chomsky di tipo 0, 1, 2 e 3.

    (b) Si consideri la grammatica G = <{a,b,c},{S,A},P,S>, dove P e'
    S → aSc | A
    A → bAc | ε
    Dire, motivando la risposta, se la stringa x=aaabbccccc appartiene a L(G).
    (b-B) Si consideri la grammatica G = <{a,b,c},{S,A},P,S>, dove P e'
    S → aSc | A
    Ac → bA | ε
    Dire, motivando la risposta, se la stringa x=aaabbc appartiene a L(G).

    (c) Si consideri la seguente Macchina di Turing M=< Γ, blank, Q, q0, F, δ > con
    Γ= {a, b, c} Q = {q0, q1, qF} F = {qF} e la funzione δ cosi' definita 
              a              b              c             blank


q0     q1 | a |D      q0 | b | D     q0 | c | D      qF | blank|I


q1     q0 | a |D
    Dire se la stringa "aabcaa" e' accettata o rifiutata da M. Giustificare la risposta

    (B) Dire se la stringa "aaccba" e' accettata o rifiutata da M. Giustificare la risposta