Topic outline

  • Summary

    The theory of automata and formal languages is one of the classical fields of theoretical computer science. It forms the basis for the development of programming languages and their analysis and translation. The roots of this theory go back to combinatorics (A. Thue, E. Post), computability (A. Turing), linguistics (N. Chomsky), and biology (A. Lindenmayer). As a formal language is just a set of words, there are potentially many different ways for describing a formal language. Here we will focus on a generative approach using formal grammars and on an analytical approach using various types of automata. A grammar tells us in detail how to generate all the words of a language, while an automaton processes an input word, accepting it if and only if it belongs to the language of that automaton. Different types of grammars and automata yield different classes of languages. Here the classes REG of regular languages, CFL of context-free languages, CSL of context-sensitive languages, and RE of recursively enumerable languages are of particular interest, as they form the famous Chomsky hierarchy. We will study various characterizations of these classes by grammars and different types of automata, consider the closure properties of these classes under various language operations, and study algorithmic problems (decision problems) for them like the membership problem, the emptiness problem, and the finiteness problem.

  • Lecture and Seminary on Thursday, Febr. 22, 2018

    Topics: - Organizational issues: course, exercises, and exams

                - A few words on the history of formal language and automata theory

                - Words, languages, and morphisms

                - Phrase structure grammars, generated language, regular grammar, right normal form

  • Lecture and Seminary on Thursday, March 1, 2018

    Topics: - Deterministic finite-state automata (DFA), accepted languages

               - closure under Boolean operations

  • Lecture and Seminary on Thursday, March 8, 2018

    Topics: - DFAs only accept regular languages

                - Nerode relation

                - Theorem by Myhill and Nerode

                - equivalence class automaton

                - minimal DFA

                - algorithm for minimizing a DFA

                - nondeterministic finite-state automaton (NFA)

                - power set construction

  • Lecture and Seminary on Thursday, March 15, 2018

    - Each regular language is accepted by an NFA

    -  The class of languages accepted by DFAs is closed under reversal

    - Right regular grammars, left regular grammars, DFAs and NFAs are equivalent

    - NFA with epsilon-transitions

    - epsilon-NFAs can be converted into equivalent DFAs

    - The class of languages accepted by DFAs is closed under union, product, and Kleene star

    - Deterministic two-way finite-state automaton (2DFA)

  • Lecture and Seminary on Thursday, March 22, 2018

    Topics: - Crossing sequences for 2DFAs

               - 2DFAs just accept regular languages

               - Moore automaton

               - Mealey automaton

               - finite-state transducer

               - finite transduction

               - rational relation

               - Theorem of Nivat characterizing rational relations

               - REG is closed under finite transductions

  • Lecture and Seminary on Thursday, March 29, 2018

    Topics:  - Regular expressions

                 - Kleene's Theorem

                 - The class of regular languages is closed under regular substitutions

  • Lecture and Seminary on Thursday, April 5, 2018

    Topics: - Pumping Lemma for regular languages

                - Applications

                - Decision problems for finite-state automata

                - context-free grammar and context-free language

                - left derivation and leftmost derivation

                - unambiguous context-free grammar and language

                - inherently ambiguous context-free language

                - syntax trees

             

    Seminary: one-hour written mid-term exam

  • Lecture and Seminary on Thursday, April 12, 2018

    Topics: - proper context-free grammar

                 - elimination of epsilon-productions from context-free grammars

                 - elimination of chain rules from context-free grammars

                 - Dyck language

                 - Chomsky Normal Form (CNF)

                 - Greibach Normal Form (GNF)

  • Lecture and Seminary on Thursday, April 19, 2018

    Topics: - Pumping Lemma for context-free languages

                - Applications

                - Context-free languages over a single-letter alphabet

                - Pushdown Automata (PDA)

                - Acceptance by empty pushdown and by final state

                - Each context-free language is accepted by a PDA

  • Lecture and Seminary on Thursday, April 26, 2018

    Topics: - PDAs only accept context-free languages

                - Closure properties of the class CFL of context-free languages

  • Lecture and Seminary on Thursday, May 3, 2018

    Topics: - Emptiness and finiteness problems for context-free grammars

                - Cocke, Kasami, Younger algorithm

                - undecidable problems for context-free grammars (preview)

                - deterministic pushdown automata (DPDA)

                - deterministic context-free languages (DCFL)

                - DCFL is closed under complementation

                - Ogden's Lemma for DCFL and applications

  • Lecture and Seminary on Thursday, May 10, 2018

    Topics: - Turing machine (TM)

                - Turing computable function

                - 1-Turing machine

                - Simulation of (multi-tape) Turing machine by a 1-Turing machine

                - nondeterministic Turing machine (NTM)

                - Simulation of an NTM by a TM

                - recursively enumerable language (RE)

                - recursive language (REC)

  • Lecture and Seminary on Thursday, May 17, 2018

    Topics: - the halting problem for Turing machines

                - encoding of 1-Turing machines

                - undecidability of the halting problem

                - Rice's theorem

                - valid computations

                - undecidable problems for context-free grammars

  • Lecture and Seminary on Thursday, May 24, 2018

    Topics: - General phrase-structure grammar

                - the class RE of recursively enumerable languages

                - closure properties

                - context-sensitive grammar

                - monotone grammar

                - Kuroda Normal Form

                - linear-bounded automaton (LBA)

                - LBA problem

                - closure properties of the class of context-sensitive languages