FORMAL LANGUAGES

1. Knowledge and understanding: students will acquire advanced knowledge relative to the formal languages theory, with respect to possible applications too. These acquirements will help students in understanding notions, results and concepts that are fundamental for a computer scientist.
2. Applying knowledge and understanding: students will develop their ability in abstraction and formalization and will acquire the expertnesses required to bite on, in a rigorous way, many applicative problems. These problems are related, for example, to the recognition of natural and artificial languages, to the string pattern matching (with important applications in bioinformatics) and to game theory.
3. Making judgements: students will be able to use the appropriate formal means in different applicative contexts, motivating their choices and autonomously developing solutions.
4. Communication skills: students will acquire more communication abilities and more control in the expressive and explanatory tools of the formal reasoning.
5. Learning skills: students will acquire the necessary, and mainly theoretical, methodologies, to afford and solve, independently, new problems in the computer science context.

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= {aⁱb^jc^k | 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.