Informatica Teorica! aiuto riduzione Linguaggi
Salve,
Sto preparando l'esame d'informatica teorica ma non riesco proprio a digerire questa definizione nonostante la sua semplicità:
"Un linguaggio L1 è detto essere riducibile ad L2 se esistente una funzione totale calcolabile $ f:{0.1}^*rarr{0.1}^* $ detta riduzione tale che per ogni stringa binaria x, $x in L1$ se e solo se $ f(x) in L2 $
1) Per definizione, si posso solo ridurre linguaggi con alfabeto di lavoro = 0,1?
2) Mi fate un esempio di riduzione tra due linguaggi?
Sto preparando l'esame d'informatica teorica ma non riesco proprio a digerire questa definizione nonostante la sua semplicità:
"Un linguaggio L1 è detto essere riducibile ad L2 se esistente una funzione totale calcolabile $ f:{0.1}^*rarr{0.1}^* $ detta riduzione tale che per ogni stringa binaria x, $x in L1$ se e solo se $ f(x) in L2 $
1) Per definizione, si posso solo ridurre linguaggi con alfabeto di lavoro = 0,1?
2) Mi fate un esempio di riduzione tra due linguaggi?
Risposte
Qual è la difficoltà "digestiva" 
che avverti?
1) E' normale trattare la IT usando linguaggi di stringhe binarie e macchine che lavorano su stringhe binarie... perché complicarsi la vita? Quindi la funzione sarà definita sulle stringhe binarie.
2) Per esempio puoi fare una riduzione fra il linguaggio Ln dei numeri naturali (espressi in binario) e Lp dei numeri pari positivi (idem).
che avverti?1) E' normale trattare la IT usando linguaggi di stringhe binarie e macchine che lavorano su stringhe binarie... perché complicarsi la vita? Quindi la funzione sarà definita sulle stringhe binarie.
2) Per esempio puoi fare una riduzione fra il linguaggio Ln dei numeri naturali (espressi in binario) e Lp dei numeri pari positivi (idem).
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo