Teorema di Rice
Il teorema di Rice afferma che “Qualunque proprietà non banale delle funzioni calcolabili è indecidibile”. Vediamolo meglio nel dettaglio. Enunciato del teorema di rice Sia F …
Pumping lemma per linguaggi context free
Il Pumping Lemma per i linguaggi context free, conosciuto anche come teorema uvwxy, dice: “Sia L un linguaggi di tipo 2 su un alfabeto T. Allora …
