CSE 350 - Assignments

Homework assignments and solutions to selected exercises, will be posted regularly throughout the semester. Exercises are from the textbook unless noted otherwise.

• Regular languages
  
  • Homework [1]: Exercises 1.4 e, 1.5 e, 1.6 l, 1.7 e, 1.13, 1.16 a, 1.18 l
  • Recommended exercises (optional): 1.31, 1.34, 1.36, 1.40, 1.41
  • Homework [2]: Exercises 1.21 b, 1.28 c, 1.29 b, 1.46 c
• Context-free languages
  
  • Homework [3]: Exercise 2.6 b, d
  • Recommended exercises (optional): 2.17, 2.19, 2.21, 2.24, 2.28 b
  • Homework [4]: Exercises 2.5 c, d, 2.9, 2.10, 2.11
  • Recommended exercises (optional): 2.12, 2.13, 2.28, 2.33
• Turing machines
  
  • Homework [5]: Exercises 2.30 d, 3.7, 3.8 b (give a state diagram)
  • Recommended exercises (optional): 3.8. c, 3.15, 3.16
  • Homework [6]: Exercises 3.9 and 3.14
  • Homework [7]: Unrestricted grammars (pdf)
• Decidability
  
  • Homework [8]: Exercises 4.2 and 4.12
  • Homework [9]: Countability (pdf)
  • Homework [10]: Exercises 5.9 and 5.12