GENERAL DESCRIPTION
The course addresses advanced topics in the context of formal language theory and possible applications. More exactly, in addition to the theoretical presentation of the formal languages and of methods to recognize, generate and elaborate them, related applicative problems will be presented. Particular attention will be addressed to the study of finite state automata, viewed as mathematical description of a discrete sequencial system, to stack automata and to Turing machines, viewed as general model of computation.
SYLLABUS
Introduction to formal languages: Grammars and recognizers.
Finite State Automata and regular languages: Finite State Automata: deterministic (DFA), nondeterministic (NFA), with epsilon-transitions. Equivalence of NFAs with and without epsilon-transitions. The class of AF-regular languages and its closure properties. Regular expressions and regular languages. Every regular language is AF-regular. The Kleene's theorem. The Pumping lemma for regular languages. Applications of the Pumping Lemma: decidability algorithms for regular languages. The Myhill-Nerode's theorem. Minimization of Finite State Automata. Applications.
Context-free grammars: Parse trees. Normal Forms for context-free grammars: eliminating useless symbols; eliminating epsilon-productions; eliminating unit production. Chomsky Normal Form: conversion of context-free grammars to Chomsky Normal Form. Greibach Normal Form (notes). Ambiguous grammars, unambiguous grammars and inherent ambiguity. Pumping Lemma for context-free languages. Applications of the Pumping Lemma for context-free languages. The Ogden's lemma (notes). The language L= {aibjck | i ≠ j, j ≠ k , i ≠ k} is not context-free. Testing membership in a CFL. Applications.
Pushdown Automata: The languages of a Pushdown Automaton: acceptance by final state and acceptance by empty stack. From Empty Stack to Final State and vice-versa. Deterministic Pushdown Automata. Equivalence of Pushdown Automata and context-free grammars (notes). Applications.
Turing Machines: Recursively enumerable languages. Deterministic Turing Machine (DTM) and Nondeterministic Turing Machine (NTM): equivalence of NTMs and DTMs. Equivalence of Turing Machines and grammars (notes).
Linear-bounded Automata and context-sensitive languages: Definitions and examples. Equivalence of Linear-bounded Automata and context-sensitive grammars (notes).
Chomsky hierarchy.
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automi, linguaggi e calcolabilità , Pearson Paravia Bruno Mondadori S.p.A. Terza Edizione, Marzo 2009.
John E. Hopcroft, Jeffrey D. Ullman. Introduction to automata theory, languages and computation, Addison-Wesley.