CPSC 390 Homework Assignments

Due Date Reading and Problems
Tuesday,
September 6
  • Read Chapter 0
  • Complete the problems 0.1-0.6, 0.8, 0.9 from class if you have not done so. (This will not be collected - just be sure you understand all of the notation and terminology.)

    The following will be handed in:

  • Write up your solution to problem 0.10 on page 27. For each step in the "proof" state whether it is a valid step (and if so why) or not valid (and if so why not).
  • Study the partially formal and partially informal proof on page 21 of Theorem 0.22 and do the following:
    • For n = 8, draw the graph that is constructed in the "proof". Be sure to label the vertices 0 through n - 1 and draw the edges that are formally defined in the set E.
    • Make the "mental picture" described in the last paragraph more formal by listing, for a general n, the edges that contribute to the degree of vertex 0 (that is, the edges vertex 0 is the endpoint of).
    • For your list above, explain why it is necessary that n be an even integer greater than 2 for this to be 3 distinct edges.
    • List the 3 edges that vertex n - 1 is the endpoint of.
    • List the 3 edges that vertex i, for 0 < i < n - 1, is the endpoint of.
  • Consider the following "mental picture" of a different graph that proves the theorem: For an even integer n > 2, let V = { 0, 1, 2, ..., n - 1}. Picture dividing the nodes into two equal sets with the even numbered nodes in one set and the odd numbered nodes in the other set. Have edges that connect the adjacent nodes in each set (with wrap-around) and edges that connect corresponding members of the two sets as illustrated below for the case of n = 6. Write this graph formally (for a general n, not just 6) as the book does for its solution. 
       --0 *  ------- * 1 ---
  |    |            |    |
  |    |            |    |
  |  2 *  ------- * 3    |
  |    |            |    |
  |    |            |    |
  |  4 * -------- * 5    |
  |    |            |    |
   ----              ----
Thursday,
Sept. 8
  • Read Section 1.1 and study the examples we didn't go over in class.
  • Do problem 0.12 on page 27 (to hand in).
  • Do the following exercises on pages 83-84 to hand in: #1.3, 1.6 (c), 1.6(e), 1.6(h), 1.6(i).
  • Try Picobot: Click here for browsers other than IE or here for IE.
Tuesday,
Sept. 13 		The following are to be turned in:
  1. Trace the computation of M1 and M2 in #1.1 (page 83) on the input string bbbabaa using the |- notation (that is, (q1, bbbabaa) |- (next state, bbabaa) |- (next state, babaa) etc. For each, conclude whether or not the machine accepts bbbabaa.
  2. Let A1 = { w | w contains the substring ab } and let A2 = { w | w contains the substring ba }.
    1. Construct DFAs to recognize each language.
    2. Use the construction from the proof of Theorem 1.25 to construct a DFA to recognize the union of A1 and A2. Write the formal description and draw the state diagram.
    3. Modify the formal description of your answer for union to define a DFA to recognize the intersection of the two languages.
    4. Does the DFA for the intersection accept the string aaabaa? Justify your answer.
  3. Do #1.4(c) on page 83.
  4. Do #1.5(c) and 1.5(g) on page 84.
  5. Do #1.14(a) on page 85.
  6. Do #1.22(a) on page 87.
  7. Do #1.24 (a), (b), (g) on page 87.
  8. Do #1.25 on page 87.
  9. Do #1.26 on page 88.
Thursday,
Sept. 15 		Hand in the following:
  1. Your re-do of problem 0.12
  2. #1.7, parts (a) - (d) and (g) on page 84.
  3. #1.11 on page 85
  4. Write a formal description of each NFA in #1.16 on page 86 (no need to do the construction asked for in the problem since we didn't do Theorem 1.39 yet).
  5. #1.36 on page 89.
Tuesday,
September 20 		Hand in the following:
  1. Pages 84 - 86,Exercises #1.8(b), 1.9(a), 1.10(a), 1.15, 1.16
  2. Pages 88 - 89, Problems 1.31, 1.32, 1.41
Thursday,
Sept. 22 		Hand in:
  1. Page 85 #1.14(a) (RE-DO formally using hints from class)
  2. Page 89, #1.36 (Also a RE-D0)
  3. Let N = ( {q0, q1, q2}, {a,b}, delta, q0, {q1, q2} ) where delta is the transition function defined by: 
                          a      b    epsilon
            ------------------------------
             q0   {q0,q1}    {}     {}
             q1      {}   {q0,q1}   {}
             q2      {}   {q1,q2}   {}
    1. Draw the state diagram for N.
    2. Trace the computation of the string aabb in N using a tree to show all paths.
    3. Is aabb in L(N)? Give reasons for your answer.

*** Start work on your lexer.

Tuesday,
Sept. 27 		Hand in:
  1. Re-do of #1.32
  2. Re-do of #1.41
  3. #1.18 (parts (a) - (f) of 1.6)
  4. #1.20
Thursday,
Sept. 29 		Hand in:
  1. #1.19
  2. #1.21
  3. #1.48
Tuesday,
Oct. 4 		Hand in (write your proofs formally!):
  1. #1.29 (a) and (b)
  2. #1.30
  3. #1.46 (a), (c)
Thursday,
Oct. 13 		Hand in: Pages 128 - 129 #2.1, 2.4(c),(d),(e), 2.6(a),(b), 2.17
Tuesday,
Oct. 25 		Page 129 #2.5(c),(d),(e), #2.7 (a),(b) (Draw the state diagram in addition to giving the description - or "name" each state with a description), #2.8
Thursday,
Oct. 27 		Hand in the following:
  1. Page 129, #2.16. Prove this using grammars; that is, assume you have two context free languages and a grammar for each. For each regular operation, use these grammars (just one of them for star) to construct a new grammar for the new language (the union of the two, the concatentation, and the star). Write out your grammars formally. Give an informal description of why your new grammars work.
  2. Page 129, #21.7 (REDO). Do this one by explicitly constructing grammars for each case in the definition of a regular expression. You may refer to your results from #2.16 for the union, concatenation, and star.
  3. Consider the language L = { ambn | m <= 2n } over the alphabet {a, b}.
    1. Construct a grammar that generates L.
    2. Explain why every string generated by your grammar is in L. Your explanation may be informal but not vague and unconvincing!
    3. Explain why every string in L is generated by your grammar. Your explanation may be informal but not vague and unconvincing!
    4. Draw a state diagram for a PDA that recognizes L. Give an informal description of what the PDA does and what each state represents.
  4. Do the same as above for the language L = {ambncpdq | m + n = p + q }
  5. Do #2.9 and 2.10 on page 129.
Tuesday,
Nov. 1 		Hand in the following:
  1. Study the PDA constructed in class by Marc and determine if it is correct. If it is, justify your answer; if it isn't, provide a counterexample that illustrates that it isn't correct.
  2. Redo #2.7(b) (that is, construct a PDA that recognizes the language).
  3. Let G be the grammar with the following production rules: 
        S -> aSb | B
    B -> bB | b
    Prove that L(G) = { ambn | 0 <= m < n }. (Use induction.)
  4. Let G be a grammar with the following production rules: 
       S -> a | Sa | bSS | SSb | SbS
    Use mathematical induction to show that every string in L(G), the language generated by G, has more a's than b's.
  5. Do #2.11. Trace the computation of the PDA on the string a + a * a (as we did in class).
Thursday,
Nov. 3 		Hand in the following:
  1. RE-DO #2.16. See instructions above. For example, your proof that context free languages are closed under union must start with two context free languages and the grammars that generate them. Then construct a grammar that generates the union. You must define each of the four parts of the grammar. Do the same for concatenation and star.
  2. RE-DO #4 from last Tuesday's homework.
  3. Do #2.2(a) on page 128
  4. Do #2.18 on page 130
  5. Do #2.30 (a), (b), and (c) on page 131. Note that there are answers to (b) and (c). You should try the problems yourself first BUT check the answer to see if you are on the right track. If you are not, re-do the problem (you may use the answer but in your own words and be sure you understand).
  6. Do #2.31 on page 131.
Tuesday,
Nov. 8 		Hand in:
  1. #3.1(c) on page 159
  2. #3.2 (d), (e) on page 160
  3. #3.5 on page 160
  4. #3.8 (a), (b), (c) on page 160 (For each, give a formal description and draw a state diagram to show the transition function.)
Thursday,
Nov. 10 		Hand in:
  1. Redo Problem #2.31 on page 131. Write a formal proof using the Pumping Lemma for Context-Free Languages.
  2. Redo the following problem: Let G be a grammar with the following production rules: 
       S -> a | Sa | bSS | SSb | SbS
    Use mathematical induction to show that every string in L(G), the language generated by G, has more a's than b's. (Write a formal induction proof.)
  3. For each of the PDAs on the sheet handed out in class determine whether the PDA accepts the complement of the given language. Be sure to test both strings it should accept and strings it shouldn't accept. If the PDA does not accept the language give an explicit string that shows it doesn't. If it does, give a convincing argument why. Your argument should include labels on the states to describe what is going on in that state.
Tuesday,
Nov. 15 		Re-do: Problem 3.8(c) on page 160. All I want is a neat, legible state diagram representing the transitions with each state labeled using words that describe what is happening in that state.

Practice Problems (these will not be handed in):

  1. #3.6 on page 160
  2. #3.15 (a), (b), (d) on page 161
  3. #3.16 (a) on page 161
  4. Describe how a PDA with two stacks can simulate a Turing Machine
  5. Construct a standard Turing machine to accept the set of all palindromes over {a, b}.
  6. Construct a two-tape Turing machine that accepts the set of all palindromes over {a, b}. Your machine should have the property that a computation on input w should take no more than 3 times the length of w plus a small constant transitions.
Thursday,
Dec. 1 		Hand in: Exercises 4.1 - 4.5 on pages 182 & 183
Friday,
Dec. 2 		Recursive Descent Parser - due by midnight
Tuesday,
Dec. 6 		Hand in:
  1. Exercise #4.6 on page 183.
  2. Show that the set { ..., -49, -36, -25, -16, -9, -4, -1, 0, 1, 4, 9, 16, 25, 36, 49 ... } (positive and negative squares of integers) is countable. Do this by first "listing" the elements in a way that you can "count", then give the actual formula for the correspondence (define the function).
  3. Show that the set { 1, 2, 4, 8, 16, 32, ...} (powers of 2) is countable. Define the function.
  4. Suppose that A and B are both countably infinite sets. Then, by definition, both may be put in one-to-one correspondence with the natural numbers. So, we may write the elements of each set using subscripts as follows: A = {a1,a2,a3,...} and B = {b1,b2,b3,...}. Show that the union of A and B is countable by showing how to "list" the elements of the union in a way that can be "counted". You may assume that A and B have no elements in common.