UMBC CMSC451, Automata Theory & Formal Languages, Spring 2007

Homework Assignments

Homework 1, Due Tuesday 02/06

1. Draw the transition diagram for a DFA D₁ for the language:

   L₁ = { w ∈ {0,1}^* | w does not contain the substring 11 }.

2. Prove that your DFA D₁ does indeed recognize L₁. That is, L(D₁) = L₁.
   Note: you must prove set containment in both direction, that L(D₁) ⊆ L₁ and that L₁ ⊆ L(D₁).

3. Draw the transition diagram for a DFA D₃ for the language:

   L₃ = { w ∈ {0,1}^* | w contains an even number of 0's and at most one 1 }.

4. Prove that your DFA D₃ does indeed recognize L₃. That is, L(D₃) = L₃.
   The note in Question 2 applies equally here.

Homework 2, Due Tuesday 02/13

1. Exercise 2.3.2.
2. Exercise 2.3.4, part b.
3. Exercise 2.3.4, part c.
4. Construct an NFA with 3 states for the following language:
   
       L = { ab, abc }^*
   
   That is, L is the set of strings w such that w is either the empty string, or w = w₁w₂w₃...w_m where each w_i is either ab or abc.

Homework 3, Due Tuesday 02/20

1. Exercise 3.1.1, parts b & c.
2. Exercise 3.1.2, part b.
3. Exercise 3.2.3.
4. Exercise 3.2.6, parts c & d.

Homework 4, Due Tuesday 02/27

1. Exercise 4.1.1, part e.
2. Exercise 4.1.2, part c.
3. Exercise 4.1.2, part e.
4. Exercise 4.1.2, part h.

Homework 5, Due Tuesday 03/06

1. Exercise 4.2.6, parts a & b.
2. Exercise 4.2.13, part b.
3. Exercise 4.3.2.
   Note: You do not have to worry about the algorithm being efficient. However, you should make sure that your algorithm doesn't run forever.
4. Exercise 4.3.4.

Homework 6, Due Tuesday 03/13

1. Exercise 4.4.2.
   
   
2. Provide CFGs for the following languages:
   
   
   1. L = { w ∈ {a, b}* | the number of a's in w does not equal the number of b's in w }
      
      
   2. L = { aⁿb^mc^k | n = m or m ≠ k }
      
      
   3. L = { aⁿb^mc^k | n + 2m = k }
   
   
3. Prove that your grammar for 2a above correctly generates the specified language.
   
   
4. Exercise 5.1.1, part d.

Homework 7, Due Tuesday 04/03

1. Exercise 6.1.1, parts b & c.
2. Exercise 6.2.1, parts b & c.
3. Exercise 6.2.3, parts a & b.
4. Exercise 6.2.6, parts a & b.

Homework 8, Due Tuesday 04/10

1. Exercise 7.2.1, part b.
2. Exercise 7.2.1, part c.
3. Exercise 7.2.1, part e.
4. Exercise 7.2.1, part f.

Homework 9, Due Tuesday 04/17

1. Exercise 7.4.1, part b.
2. Exercise 7.4.2, part b.
3. Exercise 8.2.2, parts b & c.
4. Exercise 8.2.3, parts a & b.

Homework 10, Due Tuesday 04/24

1. Exercise 8.4.3, part b.
   
   
2. Exercise 8.4.9.
   N.B.: a k-head TM does not "know" whether two (or more) of its tape heads are reading the same tape cell --- it only "knows" that the heads are reading the same symbol, which could be from different tape cells holding the same symbol.
   
   
3. Exercise 8.4.10.
   N.B.: a multi-tape TM can have only a constant number of tapes --- i.e., you are not allowed to have more tapes for longer inputs or to increase the number of tapes in the middle of a computation.
   
   
4. Exercise 8.5.1, part d.
   N.B.: by definition (in this textbook) a counter machine is deterministic.
   Hint: store 2ⁱ3^j5^k in one counter using a second counter as a "helper".

Homework 11, Due Tuesday 05/01

1. Exercise 9.1.3, part b.
2. Exercise 9.2.6, parts c & d.
3. Exercise 9.3.3.
4. Exercise 9.3.7, part b.

Homework 12, Due Tuesday 05/08

1. Exercise 9.3.4, part a.

2. Exercise 9.3.4, part b.

3. Define the language SQUARE as follows:

   SQUARE = { < M > | M is a TM and for all n, M halts in ≤ n² steps on inputs of length n }

   Show that for L_e = { < M > | M is a TM and L(M) = ∅ }, L_e ≤_m SQUARE.

4. Consider the following language concerning pushdown automata (PDAs):

   DOUBLE = { < P > | P is a PDA and L(P) contains at least one string of the form zz for some z ∈ {0,1,#}^* }

   Show that DOUBLE is undecidable. Hint: use computation histories twice.

Homework 13, Due Tuesday 05/15

1. In each of the following languages, <G_i> is an encoding of a context-free grammar. State whether each language is decidable or undecidable. Justify briefly.

   • L_a = { < G₁, G₂ > | L(G₁) ⊆ L(G₂). }

   • L_b = { < G₁, G₂ > | L(G₁) ∩ L(G₂) = Σ^*. }

   • L_c = { < G₁, G₂ > | L(G₁) ∪ L(G₂) = Σ^*. }

   • L_d = { < G₁ > | the complement of L(G₁) equals Σ^*. }

2. Exercise 9.3.4, part c.
   Note: You may use the fact that we already know certain languages are not recursively enumerable, (e.g., L_e, the complement of L_u, and the complements of the different versions of the halting problem K).

3. A set X is cofinite if its complement is finite. Every cofinite set is infinite, but some infinite sets are not cofinite. For example, the set of natural numbers larger than 10 is cofinite, but the set of even numbers is not. Define

   COFINITE = { < M > | M is a TM and L(M) is cofinite }

   Express COFINITE using ∃ and/or ∀ quantifiers over strings and/or numbers and a decidable predicate.

4. Prove that COFINITE is not decidable. Note: Prove this directly, do not use Rice's Theorem.