Automi E Linguaggi 2012/2013

Preliminari matematici: relazioni, funzioni. Gerarchia di Chomsky. Linguaggi regolari, espressioni regolari, automi deterministici e nondeterministici. Parsing dei linguaggi regolari. Linguaggi context-free e automi pushdown deterministici e nondeterministici. Parsing dei linguaggi context-free: Cocke-Younger-Kasami parser, chop-expand parser, Earley parser (optional), LL(1) parsers, LR(0) parsers, LR(1) parsers, LALR(1) parsers. Macchine di Turing e grammatiche e linguaggi di tipo 0. Grammatiche e linguaggi di tipo 1. Problemi  decidibili, indecidibili e semidecidibili. Knuth-Morris-Pratt pattern matcher. Triple di Hoare per la correttezza parziale.