## Admission Requirements

Foundations of Computer Science 1

## 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.

## Course Objectives

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.

## Time Table

The most updated version of the timetables can be found on the students' website:

## Mode of Instruction

hoorcollege, weekly practice class (which is a mandatory component of the course)

## Assessment Method

Students will be evaluated by means of a written exam and homework assignments.

The examination is worth 70% of the final grade (with a minimum of 5.5).

The remaining 30% is from the average grade of the homework assignments.

## Reading List

- John C. Martin,
*Introduction to Languages and the Theory of Computation*, 4th edition, McGraw Hill, 2010

## Registration

Aanmelden via Usis: Selfservice > Studentencentrum > Inschrijven

Activiteitencodes te vinden via de facultaire website

Voor studenten die niet staan ingeschreven voor de bachelor Informatica is er een beperkte capaciteit. Neem contact op met de studieadviseur.

## Contact information

Onderwijscoördinator Informatica, Riet Derogee