Automata and Grammars NTIN071
Section outline
-
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.
-
Transparencies for the course in the Spring Semester of 2018
(Update: May 23, 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
-
-
How to prove that a grammar generates a given language?
(Update: Febr. 22, 2018)
-
The solutions to these problems are to be presented
and discussed in the Seminary on March 1, 2018.
(Update: Febr. 22, 2018)
-
-
-
Topics: - Deterministic finite-state automata (DFA), accepted languages
- closure under Boolean operations
-
-
The solutions to these problems are to be presented and discussed in the Seminary on 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
-
-
The solutions to these problems are to be presented and discussed in the Seminary on March 15, 2018.
(Update: March 8, 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)
-
-
The solutions to these problems are to be presented and discussed in the Seminary on 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
-
-
The solutions to these problems are to be presented and discussed in the Seminary on March 29, 2018.
-
-
-
Topics: - Regular expressions
- Kleene's Theorem
- The class of regular languages is closed under regular substitutions
-
-
The solutions to these problems are to be presented and discussed in the Seminary on April 5, 2018.
(Update: March 29, 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
-
-
The solutions to these problems are to be presented and discussed in the Seminary on 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)
-
-
The solutions to these problems are to be presented and discussed in the Seminary on 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
-
-
The solutions to these problems are to be presented and discussed in the Seminary on April 26, 2018.
-
-
-
Topics: - PDAs only accept context-free languages
- Closure properties of the class CFL of context-free languages
-
-
The solutions to these problems are to be presented and discussed at the Seminary on 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
-
-
The solutions to these problems are to be presented and discussed at the Seminary on 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)
-
-
The solutions to these problems are to be presented and discussed in the Seminary on May 17.
-
-
-
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
-
-
The solutions to these problems are to be presented and discussed at the Seminary on 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
-