Homework 7

General Comments

• Problems are taken from the textbook unless otherwise noted.
• For full credit, provide context for each problem, show all calculations, and explain your work/answers.
• Numbers and/or algebra by themselves are not enough.
• You will lose a significant amount of credit if you do not show enough work/context for your answers.
• Precision is very important. You cannot skip steps, make guesses, or use flawed logic. Any of these things can lead to incorrect answers.
• Homework assignments must be very neatly written or typeset (e.g. using Word or OpenOffice).
• You must indicate any assistance you had on an assignment as specified on the Policies page.

Details

Problem	Comments
2.2a	First, you have to prove whether or not A and B are CFL. Then use that result together with Exercise 2.36 to prove the result.
2.5e	Make sure your informal description is very clear and includes all pertinent details.
2.6b	(Consider replacing with different problem)
2.12	Make sure to show any necessary work.
2.15	Don't make this harder than it is.
2.16	Make sure you do all three parts. Also, think about grammars and not PDAs.
2.19	Remove in future. The resulting grammar should be very simple.