## Goal

The course gives an introduction is an introduction to the theory of computation with emphasis on the relationships between formal languages, automata and abstract models of computation.

## Description

Automata theory and formal languages form the foundations of theoretical computer science, as they allow us to talk precisely about what is an algorithm or a computation.

An automaton is in fact a model of computation that can be defined mathematically. The simplest model that we will consider in this course is given by finite state automaton: a machine that is only able to keep track of its current state but it has no memory. Finite state automata specify an algorithmic procedure for recognizing whether a word is in a language. We will concentrate on the relationships between language recognized by a finite state automaton, language generated by a grammar and language described by a specification, and will obtain algorithms for translating one description of a language into another description of a different type.

Adding restricted form of memory to finite state automata increase their expressivity. We will study push-down automata, i.e. the class of automata with an auxiliary memory organized as a stack. In particular we will concentrate on the class of languages recognized by push-down automata, because of its major role in compiler design and parsing.

## Prerequisites

Foundation of Computer Science I

## Literature

The following book is mandatory for the course:

John C. Martin, Introduction to Languages and the Theory of Computation, 3rd edition, McGraw Hill, 2003.

## Table of Contents

- Introduction and motivation

- Formal languages
- Regular expressions
- Finite state automata

a. Distinguish one string from another

b. New automata from old - Non-deterministic finite automata

a. The powerset construction

b. Automata with empty-transitions - Kleene’s theorem

a. From finite automata to regular expressions

b. From regular expressions to finite automata - Minimal finite state automata
- The pumping lemma for regular languages
- Decision problems for regular languages
- Context-free grammars

a. Regular grammars

b. Derivation trees and ambiguity

c. The pumping lemma for context-free languages - Chomsky normal form
- Decision problem for context-free languages
- Pushdown automata

## Material

Solutions selected exercises will be provided to the students for download.

## Examination

Students will be evaluated by means of a written examination.

## Practice class

Yes, a weekly practice class is a mandatory component of the course.