CSCE 551/MATH 562
Sample Homework Exercises

The following homework is not to hand in. It can be used to prepare for the exams, which will have questions covering the 12 objective areas mentioned in the syllabus.

There are many more questions here than can probably be solved by any one person in a semester, and certainly more than can be tested for.

Homework 1:

1. Read Chapter 0
   • Exercises: 0.1(b,e,f), 0.2(a,b,e,f), 0.3(a-f), 0.4, 0.5, 0.6(e), 0.7
   • Problems: 0.10, 0.11, 0.13
   • Print and solve this Sudoku puzzle. The key to solving such a puzzle is to COMPLETELY avoid guessing. Do not fill in a square until you are certain you are entering the correct value. This is an exercise in pure deduction.
   • (Erdos-Szekeres) Let m and n be positive integers, and consider a sequence a₁, a₂, …, a_mn+1 of mn+1 many real numbers that are pairwise distinct (that is, no two entries in the sequence are equal). Show that this sequence has EITHER an increasing subsequence of length m+1 OR a decreasing subsequence of length n+1. Use the pigeonhole principle.
   • For each pair of positive integers m and n, describe a list of mn pairwise distinct real numbers a₁,…,a_mn such that every increasing sequence has length at most m and every decreasing sequence has length at most n. This shows that the Erdos-Szekeres result given above is tight.
   • Show that any way of coloring the edges of the complete graph on six vertices always has a monochromatic triangle (i.e., three edges forming a triangle and all given the same color). Hint: Use the pidgeonhole principle. (This is a special case of a much more general branch of combinatorics known as Ramsey theory.)
   • Show how to color the edges of the complete graph on five vertices red and blue to avoid a monochromatic triangle. This shows that the Ramsey theory result in the previous exercise is tight.
   Although you will not hand them in, you should do (or at least attempt) all exercises and problems in this chapter (some are much harder than others. This chapter builds up and tests your mathematical maturity, i.e., your level of comfort with the various objects and methods of mathematics -- basic logic, sets, relations, functions, graphs, etc., as well as definitions, theorems, and proofs. Mathematical maturity is the strongest indicator of success in this course.

   NOTA BENE: Any exercise appearing with an `A' before its number has a solution in the text. You should try working it first before looking at the solution. You'll appreciate the solution a lot more that way.

Homework 2:

1. Verify that the following expression for the binomial coefficient, B(n,k) : = n!/[k!(n-k)!] satisfies the recurrence equations B(n,0) = B(n,n) = 1 and B(n+1,k) = B(n,k-1) + B(n,k) for all n ≥ 0 and 1 ≤ k ≤ n.
2. Exercises 1.1, 1.2
3. Exercises 1.3, 1.4(c,e), 1.5(d), 1.6(c,l)
4. Give the transition diagram of a DFA recognizing the language of all binary strings where there are at least four 1's occuring somewhere before the third 0 (provided it exists). (So the only strings to reject are those that have at least three 0's and there are fewer than four 1's occuring before the third 0.)
5. Exercises 1.7(b,c), 1.12, 1.16(a), 1.17, 1.18(f), 1.19(b), 1.20(b,h), 1.21(a), 1.29(b)
6. Problems 1.21(b), 1.32, 1.34, 1.40(b)

Homework 3: This homework is mostly from Chapter 3, but there are a few problems remaining from Chapter 1. Automata theory provides a huge wealth of interesting exercises, from easy to very challenging and from very practical to just fun. We have only scratched the surface. (Chapter 1 alone has no less than 73 exercises and problems, and they are all worth while!) I include below a selection of some of my favorites (recommended for a good mental workout or to prepare for the CSE Qualifying Exam). Other good problems can be found in the Theory portions of past CSE Qualifying Exams. I'm happy to discuss the solutions to any of these at any time.

1. Exercises 3.2(d,e), 3.4, 3.6, 3.8(b). Problem 3.11 (argue informally).
2. Problem 3.12
3. Problems 1.51 and 1.52 cover the very practical task of DFA minimization---finding the unique DFA with the fewest states recognizing a given regular language.
4. Show how to convert a regular expression R for a language L directly into a regular expression R' for L - {ε} (that is, the set of all nonempty strings in L). The conversion is a set of recursive rules based on the syntax of R, similar to what we did in class for the string reversal construction.

   (Note: you could do this indirectly by first constructing an NFA N equivalent to R, then a DFA D equivalent to N, then a product construction of D with an automaton that accepts all nonempty strings, getting a new product DFA P, then converting P back into a regular expression R' by state elimination, say. This approach works, but is highly inefficient and may produce an overly complicated R'.)

5. The optional problems below all establish various closure properties of regular languages. For all these problems, we assume a fixed alphabet Σ.
   1. Given two strings x,y∈Σ^*, we say that x is a subsequence of y if x results from y by removing zero or more symbols and closing up the resulting gaps. That is, if y = y₁⋅⋅⋅ y_n and there exist 1 ≤ i₁ < i₂ < ⋅⋅⋅ < i_m ≤ n such that x = y_i1 ⋅⋅⋅ y_im. For any language L, define SUBSEQ(L) to be the language of all subsequences of strings in L. Show that if L is regular, then so is SUBSEQ(L). [Hint: Given a regular expression for L, there is a simple transformation to obtain a regular expression for SUBSEQ(L).] (Actually it is known, by a nonconstructive proof, that SUBSEQ(L) is regular for any language L whatsoever. To see a proof, read either of the two appendices to this paper, starting on page 34. Each appendix has a separate proof; note that λ is used to denote the empty string rather than ε.)
   2. Given two languages L₁ and L₂ over Σ, define the "quotient" language
      L₁/L₂ = { x ∈ Σ^* : (∃ y ∈ L₂) xy ∈ L₁ }.
      
      Show that if L₁ is regular (and L₂ is arbitrary!), then L₁/L₂ is regular. [Hint: Given a DFA A for L₁, define a DFA A' for L₁/L₂, where A' has all the same components as A (state set, alphabet, transition function, start state) except a possibly different set of final states.]
   3. For two strings x = x₁ ⋅⋅⋅ x_n and y = y₁ ⋅⋅⋅ y_n of the same length, define the interleave of x and y to be
      x#y = x₁y₁x₂y₂ ⋅⋅⋅ x_ny_n,
      
      and given two languages L₁ and L₂ define
      L₁#L₂ = { x#y : x ∈ L₁ ∧ y ∈ L₂ ∧ |x| = |y| }.
      
      Show that if L₁ and L₂ are regular, then L₁#L₂ is regular.
   4. For any language L and integer k ≥ 1, define L^1/k to be the language of all strings x such that x^k ∈ L (here, x^k is just xx ⋅⋅⋅ x  k times). So for example, L^1/1 = L, and L^1/2 consists of all x such that xx ∈ L. Show that if L is regular, then L^1/2 is regular. [Hint: given an n-state DFA recognizing L, construct an nⁿ⁺¹-state DFA recognizing L^1/2.]
   5. Show that if L is regular, then L^1/k is regular, for any k ≥ 1. [The previous hint also applies here.]
   6. Given a language L, define L^1/* to be the union of all the L^1/k for k = 1,2,3,…. Show that if L is regular, then L^1/* is regular. [Same hint.]
   7. Given a language L over Σ, define
      L/2 = { x ∈ Σ^* : (∃ y) |y| = |x| ∧ xy ∈ L }.
      
      Show that if L is regular then L/2 is regular. [Hint: given an n-state DFA recognizing L, construct an n2ⁿ²-state DFA for L/2.

Homework 4:

1. 3.15(d,e), 3.22, 4.2, 4.3, 4.5, 4.13, 4.16, 5.3, 5.4
2. 3.16(b,d), 4.18, 4.30
3. This problem is a variant of Exercise 3.20. Assume that M is a normal one-tape Turing machine, except that (i) on input w, the left portion of the tape initially contains $w$, where "$" is a special end marker symbol not in the input alphabet, and (ii) the machine is not allowed to write (change any symbols) anywhere in $w$ during the computation. (M is allowed to do anything it wants in the initially blank portion of the tape to the right.) Show that such a machine can only recognize a regular language. See the hint below only if you are stumped.

[Hint: Since M can easily move from one end marker to the other, we can assume WLOG that the tape head starts on the right end marker instead of the left. Fix an input w of length n, so that the left end marker is in cell 0 and the head is initially scanning the right end marker in cell n+1. For any i ≤ n, suppose that at some time step t, the head moves left from cell i+1 into cell i while entering some state q, and then at some later time t', the head moves right again from cell i to cell i+1 (for the first time since time t) and enters some state r. Note that the state r only depends on the state q (and the input w) and not on the time, since the cells j never change for any j ≤ i. Thus we can define a mapping from the states of M to the states of M based on this behavior, i.e., the mapping that sends any given state q to the corresponding r. (There's an exceptional case to consider: what if M's head never returns to cell i+1 after moving left into cell i and entering state q? In this case, q maps to one of the two halting states of M as appropriate.) Such a mapping is called a crossing sequence at cell i. Note that the set of all possible state-to-state mappings is finite and only depends on M and not on w. Note also that the total behavior of M on input w depends only on M itself and the crossing sequence at cell n, and is otherwise independent of w.

Now here's your job:
Define a DFA A whose states include all mappings from the state set of M into the state set of M. Show that, for any cell 0 < i ≤ n, the crossing sequence at cell i only depends on the crossing sequence of cell i-1 and the contents of cell i (show what this dependence is explicitly). Use this fact to define a transition function for A, so that as A reads w from left to right, when reading the i^th symbol of w, the state of A goes from the crossing sequence at cell i-1 to the crossing sequence at cell i. Make the start state of A to be the crossing sequence at cell 0 (this is clearly independent of w). What should the final states of A be??? This set is easy to define, although there is no general way of computing what it is for arbitrary M. Explain your definition of A.] )

Homework 5: High-level descriptions suffice for all algorithms.

1. Exercises 5.5 and 5.7
2. Problems 5.9, 5.12, 5.22, 5.24
3. (TRICKY: Recall that FIN_TM is the language of all < M > such that M is a TM and L(M) is finite. Define COF_TM ("COF" means "cofinite") to be the language of all < M > such that M is a TM and L(M) contains all but a finite number of strings (that is, there are at most a finite number of strings not accepted by M).
   1. Show that FIN_TM ≤_m COF_TM.
   2. Show that FIN_TM ≤_m the complement of COF_TM.
4. Exercises 7.1(a,b,e,f), 7.5, 7.10, 7.12
5. Problem 7.17

Homework 6:

1. Problems 7.22, 7.38, 7.43
2. Exercise 8.3, Problem 8.8

This page last modified Friday January 25, 2019 at 13:49:03 EST.