Smith College, CSC 250. Fall 2007. Homework Sets

• Homework 1 Due: Monday Sept 17, in class

  • Read Chapters 1 and 2
  • Textbook exercises, page 19
    numbers 2, 5, 7 ii)
  • Be prepared to talk about this homework in class.

• Homework 2 Due: Monday Sept 24, in class

  • Read Chapters 3 and 4
  • Textbook exercises:
    pages 29, numbers 8 parts a and c; and number 15.
    pages 49-50, numbers 5 part i, 6, 7
  • Extra credit, page 29 number 8 part b.
  • Be prepared to talk about this homework in class.

• Homework 3 Due: Monday Oct 1, in class

  • Read Chapters 4 and 5
  • Textbook exercises:
      Ch4 numbers 11 (all), 12 parts i and ii, 17 parts iii and iv
      Ch5 numbers 5, 6, 17

• Homework 4 Due: Monday Oct 22, in class

  • Read Chapters 6 and 7
  • Textbook exercises:
      Ch6 numbers 5, 14, 16
      Ch7 numbers 1 (do parts i through iii and show all steps for each part).
    Please show your work.

• Homework 5 Due: Monday Nov 5, in class

  • Read Chapters 9, 10, 12 (11 if you want to)
  • Page 203, number 3
  • Page 255, numbers 5, 6, and eleven
  • Page 257, number 17 parts i) and ii)

• Homework 6 Due: Monday Nov 19, in class

  • Read Chapter 14 all, Chapter 15 318-327 (to end of 327)
  • page 315, #7
  • Write a context-free grammar for the language specified in #7 part ii
  • page 316 #14
  • page 348 # 2
  • Trace the PDA you constructed in #2 on the string baaa
  • What language is accepted by your PDA (i.e. is generated by the grammar in # 2)