UMBC CMSC651, Automata Theory & Formal Languages, Spring 1997

CMSC 651 Homepage

Tuesday & Thursday 5:30pm - 6:45pm, ACIV 151

Contact Information

Instructor: Prof. Richard Chang

Homework Assignments

1. (Due 2/6) Problem 0.11, Problem 1.24, Problem 1.42.
2. (Due 2/13) Problem 1.23
3. (Due 2/20) Exercise 2.6, Problem 2.18
4. (Due 2/27) Problem 3.9, Problem 3.10, Problem 3.11
5. (Due 3/13) Exercise 5.5, Exercise 5.6, Problem 5.20
6. (Due 3/20) Problem 5.10, Problem 5.11 and the following:

   Let L1 = { < M > | L(M) = Sigma* } and L2 = { < M > | L(M) is infinite }.

   Prove that L1 and L2 are reducible to each other under mapping reductions.

7. (Due 4/3) Consider the following languages:

   L1 = { < M > | L(M) contains at least 1234 strings }

   L2 = { < M > | L(M) contains exactly 1234 strings }

   L3 = { < M > | there exists a string x such that M accepts x within 1234 steps }

   For each language prove whether the language is each of the following:
   • decidable
   • Turing recognizable
   • co-Turing recognizable
   • neither Turing recognizable nor co-Turing recognizable
8. (Due 4/17) Homework 8 is cancelled. Next homework is HW9.
9. (Due 4/24) Problem 7.21, Problem 7.30 and Problem 7.34.
10. (Due 5/1) Problems 7.29, 7.40 and 8.19
11. (Due 5/8) Problems 8.20, 9.19 and 9.21