UMBC CMSC451/651, Automata Theory & Formal Languages, Fall 2011

Homework Assignments

Homework 1, Due Tuesday 09/13

1. Exercise 1.5, part c, page 84.

2. Exercise 1.6, part a, page 84.

3. Exercise 1.6, part b, page 84.

4. Exercise 1.6, part d, page 84.

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

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

6. Prove that your DFA D₁ in the previous question 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₁).

1. Exercise 1.5, part g, page 84.

2. Exercise 1.6, part c, page 84.

3. Exercise 1.6, part f, page 84.

4. Exercise 1.6, part j, page 84.

5. 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 }.

6. Prove that your DFA D₂ in the previous question 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₂).

Homework 2, Due Tuesday 09/20

1. Exercise 1.7, parts b & c, page 84.

2. Exercise 1.8, parts a & b, page 84.

3. Exercise 1.9, parts a & b, page 85.

1. Problem 1.37, page 89.
   Note: do this just for C₃ = { x | x is a binary number that is a multiple of 3 }. Assume that x is written in the usual way — most significant digit first.
   Hint: think about the modulo operation.

2. Exercise 1.9, parts a & b, page 85.

3. Problem 1.31, page 88.
   Hint: use lots of nondeterminism.

Homework 3, Due Tuesday 09/27

1. Exercise 1.18, parts e, f & i, page 86.
   That is, give regular expressions generating the languages of Exercise 1.6 parts e, f and i.

2. Exercise 1.20, parts b, e & h, page 86.

3. Exercise 1.21, part b, page 86.

4. Use the pumping lemma for regular languages to show that the following language is not regular.

   B = { x ∈ { a, b, c }^* | the number of a's in x plus the number of b's in x equals the number of c's in x }.

5. Extra Credit: Problem 1.57, page 92.

1. Problem 1.40, part b, page 89.

2. Problem 1.57, page 92.

3. Exercise 1.18, parts e, f & i, page 86.
   That is, give regular expressions generating the languages of Exercise 1.6 parts e, f and i.

4. Use the pumping lemma for regular languages to show that the following language is not regular.

   B = { x ∈ { a, b, c }^* | the number of a's in x plus the number of b's in x equals the number of c's in x }.

Homework 4, Due Tuesday 10/04

CMSC451:

1. Consider the context-free grammar G with the following rules:

   S → aS | aA
   A → aAb | ε

   Show that L(G) is equal to L₁ = { aⁿb^m | n > m ≥ 0 } by proving these two statements by induction:

   S ⇒^* w   if and only if   w ∈ L₁
   A ⇒^* w   if and only if   w ∈ { aⁿbⁿ | n ≥ 0 }

   Make sure that you state the induction hypothesis, prove the base case and prove both directions of the "if and only if" for each statement.

2. Provide a CFG for the following language:

   L₂ = { aⁿ b^m c^k | n = m or m ≠ k }.

   Remember to document your grammar!

3. Provide a CFG for the following language:

   L₃ = { w ∈ {a, b}^* | the number of a's in w does not equal the number of b's in w }

   Note: L₃ contains strings not in a^*b^*, for example, aba ∈ L₃. Also, there might be more a's than b's or more b's than a's.
   Remember to document your grammar!

1. Question #1 for CMSC451, above.

2. Exercise 2.6, part b, page 129.
   Remember to document your grammar!

3. Provide a CFG for the following language:

   L₄ = { w ∈ {a, b}^* | the number of a's in w is twice the number of b's in w }

   Note: L₄ contains strings not in a^*b^*, for example, abaaaaabb ∈ L₄.
   Remember to document your grammar!

Homework 5, Due Tuesday 10/11

1. Use the pumping lemma for regular languages to show that the following language is not regular.

   B = { w ∈ {0,1}^* | w has odd length and the middle symbol of w is 1 }.

2. Exercise 2.13, page 129.

3. Exercise 2.14, page 129.

Homework 6, Due Tuesday 10/18

1. Give a high-level description of a pushdown automaton (PDA) for the following language and then draw the transition diagram for your PDA.

   L₂ = { aⁱ b^j c^k | i ≠ j or j ≠ k }

   Note: a high-level English description of your PDA has comments like "push X whenever a 0 is read."

2. Consider the context-free grammar in Exercise 2.1, page 128. Using Theorem 2.20, we can convert the grammar into an equivalent PDA. Let's not and say we did. Instead, trace the execution of that PDA on the following input:

   (a+a)*a+a

   At main points in the execution of the PDA where the stack changes, show the content of the stack, the position of the input head and describe the rules used to change the content of the stack. (You can ignore the transitions into the special states whose sole purpose is to push symbols on the stack. Just show the contents of the stack after the PDA is done pushing.)

3. Problem 2.22, page 130.
   Hint: use a PDA and guess how/where x and y are different.

4. Problem 2.30, part a, page 131.

5. Extra Credit: Problem 2.23, page 130.
   Note: This is not the same problem as 2.22, because there's no # in the input. That makes a big difference.

1. Give a high-level description of a pushdown automaton (PDA) for the following language and then draw the transition diagram for your PDA.

   L₂ = { aⁱ b^j c^k | i ≠ j or j ≠ k }

   Note: a high-level English description of your PDA has comments like "push X whenever a 0 is read."

2. Problem 2.20, page 130.

3. Problem 2.22, page 130.
   Hint: use a PDA and guess how/where x and y are different.

4. Problem 2.31, page 131.

5. Extra Credit: Problem 2.23, page 130.
   Note: This is not the same problem as 2.22, because there's no # in the input. That makes a big difference.

Homework 7, Due Tuesday 10/25

1. Problem 2.33, page 131.

2. Problem 2.35, page 131.

3. Problem 2.42, page 131.

1. Problem 2.25, page 130.

2. Problem 2.42, page 131.

3. Problem 2.44, page 132.

Homework 8, Due Tuesday 11/01

CMSC451

1. Problem 3.9, parts a & b, page 160.

2. Problem 3.12, page 161.

3. Problem 3.16, part b, page 161.
   Note: If A and B are Turing recognizable, then the concatenation of A and B is:

   { w ∈ Σ* | there exist x ∈ A and y ∈ B such that w = xy }.

   There is no marker between x and y. Also, the Turing machine recognizing A or B need not halt when the input string is not in its language.

1. Problem 3.12, page 161.

2. Problem 3.16, part b, page 161.
   Note: If A and B are Turing recognizable, then the concatenation of A and B is:

   { w ∈ Σ* | there exist x ∈ A and y ∈ B such that w = xy }.

   There is no marker between x and y. Also, the Turing machine recognizing A or B need not halt when the input string is not in its language.

3. Problem 3.19, page 162.
   Hint: think enumerators.

Homework 9, Due Tuesday 11/08

1. Problem 4.10, page 183.

2. Problem 4.12, page 183.

3. Problem 4.15, page 184.

1. Problem 4.10, page 183.

2. Problem 4.18, page 184.

3. Problem 4.19, page 184.

Homework 10, Due Tuesday 11/15

1. Problem 5.12, page 211.

2. Problem 5.15, page 212.

3. Recall that A_TM is defined as:

   A_TM = { ⟨ M, w ⟩ | M is a TM and M accepts w }

   Show that A_TM ≤_m-reduces to the language K₁₇ defined below:

   K₁₇ = { ⟨ M ⟩ | L(M) contains at least 17 strings }

   Note: as a consequece K₁₇ is undecidable.

1. Problem 5.15, page 212.

2. Recall that A_TM is defined as:

   A_TM = { ⟨ M, w ⟩ | M is a TM and M accepts w }

   Show that A_TM ≤_m-reduces to the language K₁₇ defined below:

   K₁₇ = { ⟨ M ⟩ | L(M) contains at least 17 strings }

   Note: as a consequece K₁₇ is undecidable.

3. Problem 5.24, page 212.

Homework 11, Due Tuesday 11/22

1. Problem 5.22, page 212.

2. Problem 5.23, page 212.

3. 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}
   EQUIV = { < M₁, M₂ > | M₁ and M₂ are TM's and L(M₁) = L(M₂). }

   Place COF and EQUIV in the Kleene Hierarchy by formulating the set using first-order quantifiers and a decidable predicate.

1. 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}
   EQUIV = { < M₁, M₂ > | M₁ and M₂ are TM's and L(M₁) = L(M₂). }

   Place COF and EQUIV in the Kleene Hierarchy by formulating the set using first-order quantifiers and a decidable predicate.

2. 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 ≤_m COF. That is FIN reduces to COF via a many-one reduction (a.k.a. a "mapping" reduction).

3. Let K = { < M, w > | M is a TM and w ∈ L(M) }. Show that there exists a TM M s.t. L(M ^K ) = FIN. That is, show that there is an oracle TM with K oracle that recognizes FIN.

Homework 12, Due Tuesday 12/06

1. Problem 6.6, page 242.

2. The textbook showed that the fixed point version of the Recursion Theorem (Theorem 6.8) can be proven using the first version of the Recursion Theorem (Theorem 6.3). Show that Theorems 6.3 and 6.8 are in fact equivalent, by proving Theorem 6.3 using Theorem 6.8.
   Note: we proved Theorem 6.8 directly in class.

3. Problem 9.13, page 362.
   Note: the result shown here can be used to prove that P ≠ SPACE[n]. See the solution for Problem 9.15.

Homework 13, Due Tuesday 12/13

1. Problem 7.11, page 295.

2. Problem 7.17, page 295.

3. Problem 7.32, page 298.

1. Problem 7.17, page 295.

2. Problem 7.32, page 298.

3. Problem 7.36, page 298.
   Note: This isn't a difficult problem. Read the note for this question and also look at the solution for 7.38.