Lun 18 Marzo, 18:25:55 - 2019

Autore Topic: Domande varie di modelli che non riesco a fare  (Letto 379 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline scheggia89

  • Studente di Dottorato
  • ***
  • Post: 156
  • FeedBack: +3/-0
    • Mostra profilo
Domande varie di modelli che non riesco a fare
« il: Mar 05 Settembre, 18:32:35 - 2017 »
Ciao a tutti,
Ho un dubbio quando bisogna definire l'automa a pila. Se ad esempio ho che la scansione della stringa non è ancora terminata ma ho la pila vuota, è possibile andare avanti con la scansione oppure termina l'automa?
 
Inoltre posto alcuni problemi di alcuni testi d'esami a cui non so dare una soluzione

1. Descrivere come opera una MTD ad un nastro che riconosce stringhe palindrome ed indicare il numero di passi che esegue in funzione della dimensione della stringa in input.

2. Come è possibile sfruttare un eventuale secondo nastro? Come cambia il numero di passi?

3. Definire con maggiore precisione possibile la categoria di linguaggi che possono essere descritti da espressioni regolari prive dell'operazione di iterazione

4. Mostrare che il problema di stabilire la soddisfacibilità di una formula in DNF è polinomiale

5. Mostrare l'indecidibilità del problema di stabilire se, dati una macchina di turing T, una stringa x e un simbolo o, la macchina T avviata sull'input x scriverà mai sul nastro il simboloo

Con riferimento al sistema assiomatico di Hilbert, dare un esempio di proposizione a che ammette una dimostrazione (di lunghezza almeno quattro) da un ipotesi: B |-H a.
N.B. B ed a possono essere scelti a piacere, purchè sussita la relazione |-H
« Ultima modifica: Lun 11 Dicembre, 19:31:57 - 2017 da scheggia89 »