UMBC CMSC451, Automata Theory & Formal Languages, Fall 2008

Homework Assignments

Homework 1, Due Tuesday 09/09

1. Exercise 1.3, page 83.

2. Exercise 1.6, part c, page 84.

3. Exercise 1.6, part e, page 84.

4. Exercise 1.6, part j, page 84.

5. Argue using a formal mathematical proof that your DFA for Exercise 1.6.j recognizes the specified language.

Homework 2, Due Tuesday 09/16

1. Exercise 1.7, part b, page 84.

2. Exercise 1.7, part c, page 84.

3. Exercise 1.9, part a, page 85.

4. Exercise 1.14, part b, page 85.

5. Problem 1.37, page 89. Note: Assume the input x ∈ {0,1}^*. This bit pattern x represents a number in base 2 (binary). We want that number to be divisible by n. Additional instructions: Construct a DFA for the n = 7 case, instead of showing C_n is regular for all n.

Homework 3, Due Tuesday 09/23

1. 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.

2. Exercise 1.16, part a, page 86.

3. Exercise 1.16, part b, page 86.

4. For two sets A and B, recall the definition of set subtraction:

   A − B = { x ∈ A | x ∉ B }

   Argue that if A and B are regular languages, then A − B must also be regular. (I.e., show that the regular languages are closed under set subtraction.)

5. Problem 1.38, page 89.

Homework 4, Due Tuesday 09/30

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, c & f, page 86.

3. Exercise 1.21, part b, page 86.

4. Exercise 1.29, part b, page 88.

5. Problem 1.46, part c, page 90.
   Hint: You might find the solution for part b helpful.

Homework 5, Due Tuesday 10/07

1. Problem 1.47, page 90.

2. Problem 1.48, page 90.
   Note: There is no typo. The language D is regular.
   Additional Instructions: Draw a DFA for the language D and explain fully why your DFA works.

3. Problem 1.49, parts a & b, page 90.
   Note: There is no marker between 1^k and y in the languages B and C. It is permissible for y to begin with a 1.
   Additional Instructions: For part a, draw a DFA for the language B and explain fully why your DFA works.

4. Exercise 2.4, part c, page 128.
   Additional Instructions: Please "document" your context-free grammar by giving an overview and by explaining the role of each variable.

5. Exercise 2.6, part b, page 129.
   Additional Instructions: Please "document" your context-free grammar by giving an overview and by explaining the role of each variable.

Homework 6, Due Tuesday 10/14

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₂ = { 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, abaaabba.

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.

4. Exercise 2.14, part b, page 129.
   

Homework 7, Due Tuesday 10/21

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₁ = { w ∈ { a, b}^* | no prefix of w has more a's than b's }

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

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

3. Give a high-level description of a pushdown automaton (PDA) for the following language

   L₁ = { w ∈ { a, b}^* | there does not exist x ∈ { a, b}^* such that w = xx }

   Note: don't draw the transition diagram for this problem.
   Hint: Let w = xx' where |x| = | x' | (i.e., x is the first half of w and x' is the second half). Your PDA can accept if it verifies that the i-th symbol of x is not the same as the i-th symbol of x'. Use nondeterminism to guess i and the finite state to remember the i-th symbol of x. This frees up the stack for checking the i-th symbol of x'. Use lots of nondeterminism.

4. Suppose that A is a context-free language and B is a regular language. Let the language C be defined as follows:

   C = { w | w ∈ A and there exists a suffix x of w such that x ∈ B }

   Argue that C must be context-free by describing a PDA for C.

Homework 8, Due Tuesday 10/28

1. Problem 2.30, part a, page 131.

2. Problem 2.31, page 131.

3. Problem 2.44, page 132.

4. Problem 2.45, page 132.

Homework 9, Due Tuesday 11/04

1. Problem 2.26, page 130.

2. Problem 3.11, page 161.
   Note: Show equivalence by showing that TM's with doubly infinite tape can be simulated by a standard 1-tape TM with semi-infinite tape. (I.e., do not rely on multi-tape TM's).

3. Problem 3.12, page 161.
   Note: Among other things, you need to show that a TM with left reset can simulate a standard 1-tape TM. Make sure that your simulation works when the 1-tape TM moves the tape head left many consecutive times (like 1000000).

4. Problem 3.14, page 161.
   Note: Make sure that you are using a single Last-In-First-Out First-In-First-Out queue. You cannot change the order of the symbols in the queue. Furthermore, note that a queue automaton cannot write on its input tape.

Homework 10, Due Tuesday 11/11

1. Problem 4.10, page 183.
   Hint: consider context-free grammars.

2. Problem 4.19, page 184.
   Note: You must fully justify the correctness of your algorithm.

3. Problem 4.28, page 184.

4. Let A = { M₁, M₂, M₃, ... } be a Turing-recognizable set of Turing machines. Argue that you can construct a decidable set B = { M'₁, M'₂, M'₃, ... } so that a language L is recognized by a TM in A if and only if L is recognized by a TM in B.
   Hint: Consider an enumerator for the set B that outputs M'₁, M'₂, M'₃, ... in lexicographic order.

5. Extra Credit: Problem 4.18, page 184.
   Note: the problem says that A and B are co-Turing-recognizable. That is, the complements of A and B are Turing-recognizable.

Homework 11, Due Tuesday 11/18

1. Exercise 5.2, page 211.

2. Problem 5.9, page 211.
   Note: Prove this directly, do not use Rice's Theorem.

3. Problem 5.14, page 212.
   Note: Consider only 1-tape Turing machines.
   Note: Rice's Theorem is not applicable to this problem because it does not involve a property of the language.

4. Problem 5.15, page 212.
   Note: Consider only 1-tape Turing machines.

Homework 12, Due Tuesday 11/25

1. Problem 5.22, page 212.

2. Problem 5.23, page 212.

3. Problem 5.24, page 212.

4. Problem 6.6, page 242.
   Hint: Use the recursion theorem instead of re-proving it.

Homework 13, Due Tuesday 12/09

1. Problem 6.23, page 243.

2. Problem 7.17, page 295.

3. Problem 7.21, page 296.
   Hint: given a Boolean formula φ construct a new formula φ' with exactly one more satisfying assignment (i.e., the number of satisfying assignments in φ' is 1 plus the number of satisfying assignments in φ).

4. Problem 7.32, page 298.
   Note: The hard part of this problem is showing that U is a language in NP. To make this simpler, let's change the definition of U slightly:

   U = { (M, x, #^t) | N_u accepts input < M, x > within t steps on at least one branch }.

   Here N_u is a nondeterministic version of the universal Turing machine that simulates M on input x directly.