Smith College, CSC 250. Spring 2011. Homework Sets

• Homework 1 Due: Friday Jan 28, in class

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

• Homework 2 Due: Friday Feb 5, in class

  • Read Chapters 3 and 4
  • Textbook exercises:
    page 19, 7 ii)
    pages 29, numbers 8 parts a and c; and number 15.
    

• Homework 3 Due: Friday February 11, in class

  • Read Chapters 4
  • Read this article: Wikipedia on Regular Expressions
    The first part is on regular expression theory. The second part is on regular expressions in programming languages, used for pattern matching.
  • Textbook exercises:
       pages 49-50, number 5, number 6, and number 7
    and 17 parts iii and iv

• Homework 4 Due: Friday February 25, in class

  • Read Chapter 5 and 6
  • Use alphabet {a,b} for all problems.
      Ch5 numbers 5, 6, 14, and 19.
    Please show your work.

• Homework 5 Due: Friday Mar 4, in class

  • Read Chapter 6
  • Textbook exercises:
      
  •   Ch6 Number 1. Follow directions, but only for the FA in Problems 17 and 19 (of ch5).
      Ch6 numbers 14, 16

• Homework 6 Due: Friday March 25, in class

  • Read Chapter 7
  • Textbook exercises:  Ch7 numbers 1 (do parts i, iii, and vi and show all steps for each part).
    Please show your work.
  • Read Chapter 9
  • Textbook exercises:
      Ch 9 numbers 1 and 2.
    Please show your work.
  • Read Chapter 10 - just the first half, on the pumping lemma.
  • Textbook exercises:
      Ch 10 numbers 1 parts i and iii.
    
  • Look over the problems at the end of chapter 10 to see many examples of languages that are not regular. Don't do the problems, just look over the languages.

• Homework 7 Due: Friday April 1, 2011, in class

  • Read Chapter 12
  • Page 255-256, numbers 3 (hint, both languages are regular), 6, and 11.
  • Page 257, number 16 parts i) and ii).
    Note: A syntax tree is the same thing as a parse tree.

• Homework 8 Due: Friday April 9, 2011, in class

  Due: Friday April 9, in class
  • Read Chapter 14 all, and 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, and # 7
         For number 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)?
    Note:These two problems require converting the grammar to Chomsky Normal Form (CNF) first, using Theorem 26 pg 278 (and class notes).

• Homework 9 Due: Friday April 15, in class

  Read Chapter 19. We will do page 454, number 1 in class Wednesday.
  • page 454, number 2
  • page 454, either 3 or 6 (you choose)