Teoremi di Calcolabilità e Proprietà dei Programmi

I testi forniti esplorano i fondamenti dell'informatica, concentrandosi sulla teoria della computazione e dei linguaggi formali. Il primo estratto introduce concetti come le Macchine di Turing (MdT), automi deterministici e non deterministici (DFA e NFA), e la struttura dei linguaggi. Il secondo, un manuale universitario, espande su questi argomenti, trattando in dettaglio i linguaggi regolari (con proprietà e minimizzazione di DFA), le grammatiche libere dal contesto (CFG), e la teoria della calcolabilità (MdT, funzioni ricorsive, classi di complessità come P, NP, EXPTIME e PSPACE). Si affrontano anche riducibilità, problemi NP-completi e teoremi di ricorsione, con accenni alla metaprogrammazione e agli interpreti. L'ultimo frammento sembra essere un appunto su automi e linguaggi regolari, con esempi ed esercizi sulla loro verifica e costruzione.