Prospectus

nl en

Foundations of Computer Science 2

Course 2015-2016

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

Het meest recente rooster is te vinden op de LIACS website

Mode of Instruction

Lecture (hoorcollege) and weekly practice class(werkgroep).

Assessment Method

Students will be evaluated on the basis of a written examination, complemented with take-home assignments.

Reading List

  • The following book will be used for the course: John C. Martin, Introduction to Languages and the Theory of Computation, 3rd edition, McGraw Hill, 2003
  • Extra material and solutions of selected exercises will be provided to the students for download

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

Website

Fundamentele Informatica 2