UMBC CMSC651, Automata Theory & Formal Languages, Spring 1999

CMSC 651 Homepage

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

Course Information

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

• Course Description

• Couse Syllabus

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

Homework Assignments

1. (Due 02/09) 1.4(e, f, & l), 1.12, 1.24, 1.42

2. (Due 02/16) 1.17, 1.23

3. (Due 02/23) 2.4(a, c, d, f), 2.6(a, c)

   ---

4. (Due 03/18) 2.18(a,b,c,d), 3.12, 4.11, 4.18

5. (Due 04/01) 5.10, 5.12, 5.20, and the following problem.

   Prove that ALL is equivalent to EQUIV under mapping reductions, where:

   ALL = { < M > | Turing machine M accepts all strings }

   EQUIV = { < M₁, M₂ > | M₁ & M₂ are Turing machines and L(M₁) = L(M₂) }

6. (Due 04/08) 6.5, 6.6 and the following problem.

   Prove directly that A_TM mapping reduces to FINITE and the complement of A_TM mapping reduces to FINITE, where:

   FINITE = { < M > | L(M) contains a finite number of strings }

   ---

7. (Due 04/27) 7.30, 7.39 and prove the following language is NP-complete.

   FAS = { (G,k) | G = (V,E) is a directed graph, k <= |E|, and there exists a subset E' of E such that |E'| <= k and E' contains at least one edge from each cycle in G. }

   Note: FAS = Feedback Arc Set. Also, there can be exponentially many cycles in a directed graph, so be careful when you show that FAS is in NP.

   Optional: Show that the following language is NP-complete (instead of FAS).

   Set_Basis

   Instance:

   a collection C of subsets of a finite set S and a positive integer K <= |C|.

   Question:

   Is there a collection B of subsets of S with |B| = K such that for each X in C, there is a subcollection B' of B such that X is exactly the union of the sets in B' ?

   Technically, Set_Basis is the language consisting of the triples (C, S, K) such that C has a set basis (as defined above) of size K. Hint: reduce from Vertex Cover. Second Hint: you can make the reduction work by constructing a collection C where each element of C has <= 3 elements from S.

8. (Due 05/04) 8.19, 9.3, and prove the following statement

   NP is not equal to SPACE[n⁹].

9. (Due 05/11) 9.12, 10.11, 10.13