### General Information

Course Code | X_401049 |
---|---|

Credits | 6 EC |

Period | P4 |

Course Level | 300 |

Language of Tuition | English |

Faculty | Faculty of Science |

Course Coordinator | drs. J. Endrullis |

Examiner | drs. J. Endrullis |

Teaching Staff |
drs. J. Endrullis |

### Practical Information

You need to register for this course yourself

Last-minute registration is available for this course.

Teaching Methods | Seminar, Lecture |
---|

Target audiences

This course is also available as:

### Course Objective

The student is acquainted with important notions and algorithmsregarding

formal languages, automata, grammars, compilers, computability and

complexity.

This course addresses foundational questions in computer science, such

as:

- "What is a (programming) language?",

- "How can languages be recognised by computers (automata)",

- "Which problems can be solved using a class of automata?",

- "How much time and memory does solving a problem require?".

The course is divided into the following parts: automata & languages and

computability theory.

### Course Content

The first part, on automata and languages, deals with the concepts offormal language, grammar, and automaton. Two types of languages are

covered: regular and context-free languages. Regular languages are used,

e.g., in search queries, in the form of regular expressions.

Context-free languages are suitable to describe programming languages.

The automata-theoretic counterparts here are finite automata and the

more powerful pushdown automata. Pumping lemmas are discussed to

determine whether a language is regular or context-free. With each type

of language a class of grammars is associated: left-linear and

context-free grammars. Parsing algorithms are presented for context-free

languages, to determine whether a string is in the language.

In the second part of the course, on computability theory, the central

question is "Which computations can be performed on a computer?". To

reason about this question, Turing machines are introduced, as well the

Church-Turing thesis, along with examples of undecidable problems: the

halting problem and the Post correspondence problem. It is shown how

undecidability of new problems can be shown by reduction from a known

undecidable problem. Important complexity classes from the complexity

hierarchy are discussed, notably P, NP, and NP-complete, together with

the corresponding reduction arguments.

### Teaching Methods

4 hours per week lectures; 4 hours per week exercise classes### Method of Assessment

The homework is mandatory for qualifying for the exam (70% of thehomework points to qualify for the exam). In case at least 90% of the

homework points is obtained, 0.5 bonus point is awarded for the final

grade.

At the end of the course there is a final exam. The overall grade is the

grade of the final exam plus the possibly 0.5 bonus point obtained for

the homework. (The bonus is only added for students that pass the exam

with a grade of at least 5.5.)

There is no resit opportunity for the homework.

### Literature

Peter Linz, An Introduction to Formal Languages and Automata, Jones &Bartlett, 4th or 5th edition