Linguaggi formali ed i fondamenti dell'informatica

I testi forniti esplorano i fondamenti teorici dell'informatica, concentrandosi principalmente sulla teoria dei linguaggi formali e sulla teoria della calcolabilità. Discutono i linguaggi regolari e i linguaggi liberi dal contesto, con particolare attenzione al Pumping Lemma come strumento per dimostrare la non-regolarità o non-contestualità di un linguaggio. Vengono esaminati diversi tipi di automi, come gli automi a stati finiti (deterministici e non) e gli automi a pila, spiegando la loro equivalenza e le proprietà dei linguaggi che possono riconoscere. La documentazione introduce anche la Gerarchia di Chomsky, classificando le grammatiche e i linguaggi in base alla loro complessità. Infine, i documenti approfondiscono i concetti di ricorsività, inclusi gli insiemi ricorsivi, ricorsivamente enumerabili e non ricorsivamente enumerabili, toccando la tesi di Church-Turing, il Teorema di Rice e la riducibilità, che definiscono i limiti di ciò che è computabile.