Assigned:
Wed 10 Mar 2004
Due:
Wed 17 Mar 2004
Problem | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | ... |
---|---|---|---|---|---|---|---|---|---|---|
Credit | RC | RC | RC | EC | RC | RC | NA | RC | RC | ... |
where "RC" is "regular credit", "EC" is "extra credit", and "NA" is "not applicable" (not attempted). Failure to do so will result in an arbitrary set of problems being graded for regular credit, no problems being graded for extra credit, and a five percent penalty assessment.
Required: 6 of the following 8 problems
Points: 18 pts per problem
Hint: Review undecidability results for CFLs using PCP.
Show that no such algorithm for PDAs exists. Specifically, you should formulate a language L which could be decided by such an algorithm and then prove that the language L is undecidable; thus, the algorithm in question cannot exist.
Hint: We showed in class that that the following language was undecidable.
Hint: Construct a directed graph with one vertex for each possible literal and directed edges corresponding to constraints. Test for a particular graph property.