Assignments for Cosci 30a: Theory of Computation

• Textbook:

  

  • Introduction to the Theory of Computation, Second Edition
    Michael Sipser. Thomson Publishing, Boston 2006
  • Errata

Assignment 11

• Read Chapter 10
• Do Excercises:
  • 10.1
  • 10.2
• Do any three of the following Problems
  • 10.11
  • 10.12
  • 10.14
  • 10.15

Assignment 10

• Read Chapter 9.
• Do Excercises:
  • 9.4
  • 9.5
  • 9.6
  • 9.7 e, g, h
  • 9.8
  • 9.10
  • 9.11
• Do Problems
  • 9.19
  • 9.20
  • 9.24
  • 9.25

Assignment 9

• Read Chapter 8
• Do Excercises:
  • 8.1
  • 8.2
  • 8.3
  • 8.4
  • 8.6
• Do Problems
  • 8.11
  • 8.17
  • 8.20
  • Either 8.27 OR 8.28 (your choice)
• Extra Credit
  • 7.26
  • 8.14

Assignment 8

• Read Chapter 7
• Do Excercises:
  • 7.1
  • 7.2
  • 7.5
  • 7.6
  • 7.7
  • 7.11
• Do Problems
  • 7.13 (hint: this is almost the same as 7.12)
  • 7.17
  • 7.21
  • 7.30
• Extra Credit - see notes from 27 March.

Assignment 7

• Read Chapter 6
• Do Excercises:
  • 6.1 You can get credit for pseudo-code. This doesn't have to compile under any real language.
  • 6.2
  • 6.4
• Do Problems:
  • 6.6
  • 6.7
  • 6.18
  • 6.21 You may assume the result of 6.20.
• Extra Credit: Do excercise 6.1 in C or Java, and show that it compiles and runs correctly. There are a few tricky parts here to get everything to compile.

Assignment 6

• Read Chapter 5
• Do Excercises:
  • 5.1
  • 5.2
  • 5.3
  • 5.4
• Do Problems:
  • 5.13
  • 5.17
  • 5.20
  • 5.35

Assignment 5

• Read Chapter 4
• Do Excercises
  • 4.2
  • 4.4
  • 4.6
  • 4.7
  • 4.8
• Do Problems
  • 4.16
  • 4.19 (hint: Use the result from 4.16)
  • 4.22
  • 4.27

Assignment 4

• Read Chapter 3
• Do Excercises
  • 3.1
  • 3.2
  • 3.4
  • 3.6
  • 3.7
  • 3.8
• Consider the languages in Excercise 3.8. For each one, is it regular? Is it context-free? Prove your answers.
• Do Problems
  • 3.9
  • 3.11
  • 3.12
  • 3.13
  • 3.14
  • 3.15
• I mentioned in class two different definitions for Context Sensitive Grammars: In one the LHS of the rule had to be no larger than the RHS, In the other, rules were of the form &alpha A &beta -> &alpha &beta &gamma where A is a non-terminal; &alpha and &gamma are in V* and &beta is in V+. Clearly all rules of the second form are of the first form. Show that one can express the rule
  AB -> BA
  using rules of the second form. This is not a formal proof that the two forms are equivalent, but it's the hard part of that proof.
• Extra Credit Complete the proof that the two definitions of Context Sensitive Grammars are equivalent. Note that you do not need to solve the first part of this problem to get the extra credit part.

Assignment 3

• Read Chapter 2
• Do Excercises
  • 2.1
  • 2.2 (note: You only need the result of Example 2.36, you don't need to know the technique for this problem.)
  • 2.9
  • 2.10
  • 2.11
  • 2.13
  • 2.15
  • 2.16
• Do Problems
  • 2.31
  • 2.35
  • 2.43
  • 2.44

Assignment 2

• Read Sections 1.3 and 1.4 (pages 63 - 82)
• Do Excercises:
  • 1.18
  • 1.19 a, c
  • 1.20 a, c, e, f, h(h is a little tricky)
  • 1.24 a, c, e, h
  • 1.28
  • 1.29 b (This is an important problem, you should do a and c as well, but we won't grade them.)
  • 1.30
• Do Problems:
  • 1.51
  • 1.53
  • 1.60
  • 1.61
  • 1.63 (If you can't do part a, assume it and do part b, which is easier.)
• Extra Credit:
  • 1.57
  • 1.58

Assignment 1

• Skim Chapter 0.
• Read Sections 1.1 and 1.2 (pages 31 - 62)
• Do Excercises
  • 1.3
  • 1.5 c, d, e
  • 1.6 e, g, i, j, m
  • 1.8 a
  • 1.9 a
  • 1.12 - only give the DFA, the Regular Expression is not required.
  • 1.16
• Do Problems:
  • 1.31
  • 1.43
  • 1.48

Assignment 0

• Buy Textbook.
• Come to class.