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.

Introduction to formal languages:

Grammars and recognizers.

Finite state automata and regular languages:

Finite state automata: deterministic, nondeterministic, with epsilon-transitions.

The class of AF-regular languages.

Regular expressions and regular languages.

Kleene's theorem.

Pumping lemma for regular languages.

Pumping Lemma and decidability algorithms for regular languages.

Myhill-Nerode's theorem.

Context-free grammars:

Parse trees.

Simplification of context-free grammars: useless symbols; epsilon-productions; unit-productions.

Chomsky Normal Form.

Greibach Normal Form.

Ambiguous, non-ambiguous and inherently ambiguous grammars.

Pumping Lemma for context-free languages.

Ogden's Lemma.

Membership problem for context-free languages.

Pushdown Automata:

Acceptance by final state and by empty stack.

Deterministic pushdown automata.

Pushdown automata and context-free grammars.

Turing Machines:

Recursively enumerable languages.

Deterministic e non-deterministic Turing Machines.

Turing Machines and unrestricted grammars.

Linear-bounded automata and context-sensitive languages:

Definition and examples.

Linear-bounded automata and context-sensitive grammars.

Chomsky Hierarchy

1) John E. Hopcroft, Rajeev Motwani, Jeffrey D Ullman. Automi, linguaggi e calcolabilità , Pearson Paravia Bruno Mondadori S.p.A. Terza Edizione, Marzo 2009.

2) John E. Hopcroft, Jeffrey D Ullman. Introduction to automata theory, languages and computation, Addison-Wesley