Bridging Course Foundations of Informatics

Lecture · Master

Winter Term 2017/2018
Teachers: Erika Ábrahám

Foundations of Informatics – Formal Languages and Processes

This page covers the third week of the Foundations of Informatics Bridging Course in Winter Semester 2017/18, held in Spring 2018 at b-it, Bonn.

Contents

The following topics are covered:

Objectives

After passing this part of the course, participants are expected to have acquired the following skills:

  1. Regular Languages:
    • to give the basic definitions of finite automata and regular expressions;
    • to construct a finite automaton or a regular expression from a given language specification;
    • to translate a regular expression into an equivalent finite automaton;
    • to compute the set of reachable states of a finite automaton with respect to a given input word;
    • to remove ε-transitions from a finite automaton;
    • to apply the powerset construction to turn a nondeterministic finite automaton into a deterministic one; and
    • to minimize a given deterministic finite automaton.
  2. Context-Free Languages
    • to give the basic definitions of context-free grammars and pushdown automata;
    • to construct a context-free grammar or a pushdown automaton from a given language specification;
    • to turn a given context-free grammar into Chomsky normal form;
    • to apply the CYK algorithm to decide the word problem for a context-free grammar;
    • to apply the marking algorithm to decide the emptiness problem for a context-free grammar; and
    • to translate a context-free grammar into an equivalent pushdown automaton.

Material

The following textbooks provide additional information.