UMBC CMSC651, Automata Theory & Formal Languages, Spring 2000

CMSC 651 Homepage

Tuesday & Thursday 4:00pm - 5:15pm, SS208

Course Information

• Instructor: Prof. Richard Chang   (chang@umbc.edu).
  Office: ECS 225c   (410) 455-3093.
  Office Hours: Tue & Thu 3pm - 4pm

• Course Description

• Couse Syllabus

• Errata for the textbook: (first printing), (second printing).

Homework Assignments

HU = Introduction to Automata Theory, Languages and Computation, Hopcroft & Ullman, 1979.

1. (Due 02/08) 1.4 (f, h & i), 1.17, 1.24. Optional: 1.32.

   Note: for people with the first printing of the textbook, Ex 1.17(b) should read "{ www | ...}" (3 w's instead of 2).

2. (Due 02/15) 1.23, 1.31, 1.42

   Note: for people with the first printing of the textbook, in Prob 1.23(d), the string w is in {0,1}* (the * is missing).

   Optional: [HU Ex 3.18, p. 73] Show that if L is regular, then so is the following language:

   LOG(L) = { x | for some y with |y| = 2^|x|, xy is in L }

3. (Due 02/22) 2.6 (b & d), 2.18 (c), 2.17. Optional: 2.27.

   ---

4. (Due 03/14) 3.10, 4.19, 5.12.

5. (Due 03/28) 5.20 and the following two problems:

   • Show that K₁₇ defined below is many-one complete for the Turing recognizable languages.

     K₁₇ = { <M> | <M> is an encoding of a Turing machine and |L(M)| >= 17 }

   • Show that ALL_TM and INF_TM defined below are equivalent under many-one reductions.

     ALL_TM = { <M> | <M> is an encoding of a Turing machine and L(M) = Sigma^* }

     INF_TM = { <M> | <M> is an encoding of a Turing machine and L(M) contains an infinite number of strings}

6. (Due 04/04) 4.18, 5.21 and the following problem:

   A set is cofinite if it is the complement of a finite set. Let

   COF = { < M > | M is a TM and L(M) is cofinite}
   FIN = { < M > | M is a TM and L(M) is finite}

   Prove that FIN reduces to COF via a many-one reduction.

   ---

7. (Due 04/25) 7.21, 7.27, 7.29

8. (Due 05/02) 8.19, 8.20, 9.3

9. (Due 05/09) 9.19, 9.20, 9.21