Smith College, CSC 250. Spring 2013. Homework Sets

• TA: Shannon MacKenzie
• Help Session: Sundays 2-4 Ford Hall 342
  

• Homework 1 Due: Monday Feb 4, in class

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

• Homework 2 Due: Monday Feb 11, in class

  • Read Chapters 3 and 4
  • Textbook exercises:
    pages 28-29, numbers 7, 16, 19 parts i and iii.
    page 49, numbers 4, 7, 10.

• Homework 3 Due: Monday February 25, in class

  • Read Chapter 5
  • Textbook exercises:
       page 71, numbers 1-4
    

• Homework 4 Due: Monday March 4, in class

  Please show your work.
  • Read Chapters 5 and 6 and part of 7
  • Review this class example (now finished)
    • REfromTGexpage1.jpg
    • REfromTGexpage2.jpg
  • Use alphabet {a,b} for all problems.
  • Textbook exercises:
  •   Review a little ch4: Page 50, number 17 parts iii and iv
  •   Chapter 5, page 73, number 15 and page 74 number 19
      Ch6 page 89, numbers 6, 9, 10
  •   Ch7 page 142, numbers 1 (do parts i, iii, and vi and show all steps for each part).
    

• Homework 5 Due: Monday March 11, in class

  Please show your work.
  •   Chapter 7 page 142
        number 1 part iv)
  •   Chapter 7 page 143
        number 3 part i) and number 5 part ii)
  • jpgs of solutions:
    hw5Page1.jpg
    hw5Page2.jpg
    hw5Page3.jpg
    

• Homework 6 Due: Monday April 1, 2013, in class

• Read Chapter 12
• Textbook exercises:
    page 255 number 6
    page 256 numbers 10 and 15 parts i -> iv for all CFG 1. -> CFG 5..
  Please show your work and make sure you draw the syntax trees (not the total language trees).
  
    Page 257, number 16, parts i) and ii). Show two different syntax trees for the word you find in each of the parts.
  
• Read Chapter 10 - just the first half, on the pumping lemma.
• 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.
• Extra Credit: Textbook exercise:
    Ch 10 number 10 part i only.
  

Homework 7 due April 8, Monday

• Read Chapter 13, and 14
• page 287, number 11, part iii
• page 287, number 13, part ii (for extra credit)
• page 287, number 14, part iv
• page 314, number 5, and number 6 parts i and ii
• page 315, Write a context-free grammar for the language specified in #7 part ii (for any n,m independent integers - ignore the 2,1 in that problem). You don't have to explain how the machine accepts it.

Homework 8 due April 19, Friday (New Due Date)

• Reading: chapters 15,16 (especially the pumping lemma for CFGs), and chapters 19 and 23.
• 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).
• page 374, number 9

The final project is a presentation to the class
on the topic you have selected. You can choose 
to use powerpoint/html/programming interface,
whatever works, including the whiteboard in 
order to get the ideas across clearly.

There is no paper to write.

Part of the project grade is attending all of the 
presentations. 

Presenations should be 15 minutes long.