CS373: Intro to Theory of Computation
Spring 2010 - Professor Madhusudan Parthasarathy
Skills list for the second midterm
The second midterm will cover material from lecture 9 through lecture 17.
The primary focus of the exam will be topics that were not
covered on the first midterm. These include suffix languages, minimization
of DFAs, proving non-regularity of languages directly
(using MNT or pumping lemma) as well as by using closure properties of
regular languages, algorithms on DFAs/NFAs/RegExp, Turing machines,
designing Turing machines (both low-level and high-level), universal
Turing machines, recognizability vs decidability, undecidability, and
simple reductions for proving undecidability of languages.
You are expected to also remember basic facts from earlier in
the course that were covered in Midterm#1, but the exam won't probe
for details that are easy to forget.
Here is a summary of the key new skills that will be tested on the midterm:
DFA minimization
- For a fixed language L, know that there is a specific minimum
number of states for any DFA recognizing L.
- Compute the suffix language Lq
for each state q in a specific DFA.
- Mimimize a DFA by merging states with the same (suffix) language.
Regular and non-regular languages
- Know the examples of non-regular languages given in lecture and Sipser.
- Tell whether a specific language L is regular.
Examples of non-regular langauges will be like
(but perhaps not identical to)
those in lecture notes, section 1.4 in the book, homeworks.
- You won't be expected to know the pumping lemma for regular languages.
- You should be able to prove a given language L is not regular;
you can do this using the MNT proof (preferred and encouraged)
or use the pumping lemma.
- Use closure properties to prove that a language is not regular,
given a "seed" language already known not to be regular.
- Know basic algorithms for representations of regular languages
(Lecture 11), like emptiness of DFAs, checking inclusion, etc.
Turing machines
- Formalism: tuple notation, configurations, accepting
sequences of configurations.
- Definition of Turing-recognizable and Turing-decidable,
and especially how they differ.
- Given a Turing machine's state diagram, describe the machine's
behavior and language. Produce a sequence of
configurations for a specific input string.
- Design a Turing machine that accepts a specific language,
and/or behaves in a specific way.
Describe it using a state diagram (very simple problems only!) or
pseudo-code.
Simulations
- Simulating a new type of Turing machine with a normal one, e.g.
multiple tapes, doubly-infinite tape, preloaded constant string.
- We're not going to make you produce a long, complex construction
in full detail. Rather, concentrate on understanding the key ideas
in the above constructions and theorem proofs.
Encodings
- Encode a graph or other complex data structure as a string.
- Encode a machine (DFA, RA, Turing machine, etc) as
a string or file.
- Specific details of the particular encoding don't matter. Understand
the general concept of how encodings are designed.
- Define a computation history and explain what's involved in checking that it's valid.
Decidable and undecidable problems
- Know the definitions of standard decision problems involving regular languages, context-free
languages, Turing machines, linear-bounded automata.
E.g. EDFA, ATM. See sections 4.1 and 5.1 of Sipser.
- Classify each of these standard problems as decidable, Turing recognizable,
not recognizable but the complement is recognizable, or none of these.
- For the decidable or recognizable problems, sketch an algorithm that decides or
recognizes it. (Efficiency doesn't matter.)
Proving languages undecidable
- Know that a language is decidable if and only if the language
and its complement are both recognizable.
- Know that decidable languages are closed under complement, but
recognizable languages aren't.
- Closure properties of recognizable and decidable languages.
- Prove that a language is undecidable or not recognizable, using a
simple proof by contradiction that relies on closure properties or
similar basic facts.
- Understand the diagonalization proof that
ATM is undecidable. You don't have to be able
to construct a whole proof like this from scratch.
- Know how to prove that a language is undecidable using
a reduction from another language already known to be
undecidable. Proofs on the exam are likely to have a
very simple outline (up to the level covered in Lecture 17).