UMBC CMSC451, Automata Theory & Formal Languages, Fall 2005

Homework Assignments

Homework 1, Due Tuesday 09/13

1. Exercise 2.2.4, parts b & c. Draw transition diagrams.
2. Exercise 2.2.5, parts b & d.
   For part b, give a mathematical definition of the transition function delta. For part d, draw an transition diagram.
3. Explain why your solution to 2.2.5.d is correct. Recall that to argue that a DFA M recognizes a language A, you need to argue that L(M) is contained in A and that A is contained in L(M).
4. Exercise 2.2.8, parts a & b.

Homework 2, Due Tuesday 09/20

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 09/27

1. Exercise 3.1.1, parts b & c.
2. Exercise 3.1.2, part b.
3. Exercise 3.2.3.
4. Exercise 4.1.2, parts c & f.

Homework 4, Due Tuesday 10/04

1. Exercise 4.1.2, parts b & g.
2. Exercise 4.1.4, part d.
3. Exercise 4.2.6 part c. Note: This one requires thinking.
4. 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.

Homework 5, Due Tuesday 10/11

1. Exercise 4.4.2.
   
   
2. Give context-free grammars for the following languages. Please comment your productions.
   
   
   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 6, Due Tuesday 10/18

1. [From Introduction to the Theory of Computation, 2/e, by M. Sipser]
   Consider the following context-free grammar G:

   S → T T   |   U
   T → 0 T   |   T 0   |   #
   U → 0 U 00   |   #
   

   1. Give an English description of L(G).
   2. Prove that L(G) is not regular.
   
   
   
2. Exercise 5.1.4, parts a & b.
   
   
3. Exercise 5.2.2.
   
   
4. Exercise 5.4.5, parts a & b.

Homework 7, Due Tuesday 10/25

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 11/01

1. Exercise 6.3.5, parts a & b.
2. Exercise 7.2.1, parts b & c.
3. Exercise 7.2.1, part e.
4. Exercise 7.2.1, part f.

Homework 9, Due Tuesday 11/08

1. Exercise 7.1.3.
   
   
2. Exercise 7.1.9, part a.
   
   
3. [From Introduction to the Theory of Computation, by M. Sipser]
   Let G be a context-free grammar in Chomsky Normal Form that has b variables. Show that if G generates a string using a derivation with at least 2^b steps, then L(G) is infinite.
   
   
4. Exercise 7.3.2, parts a & b.

Homework 10, Due Tuesday 11/15

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

Homework 11, Due Tuesday 11/22

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 b. Not 8.5.5 as previously posted.

Homework 12, Due Tuesday 12/06

1. Exercise 9.1.3, part b.
2. Exercise 9.2.6, parts b and c.
3. Exercise 9.3.4, parts a and b.
4. 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.

Homework 13, Due Tuesday 12/13

1. Exercise 9.3.4, part c. Note: part a was already assigned for HW12.
   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).
   
   
2. 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.
   
   
3. Prove that COFINITE is not decidable. Note: Prove this directly, do not use Rice's Theorem.
   
   
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 Extra Credit (optional), Due Tuesday 12/13

1. Exercise 5.4.2
2. Exercise 7.2.3.
3. Exercise 7.2.5, part a.
4. Exercise 7.3.4, part d.