CSCI 338: Homework 4
The problems selected for careful grading were #2 (3 points) and
#3 (4 points).
Problems - This homework set is complete
- Problem 2.30, part (a) on page 157.
- Prove that language P = {ak | k is a prime number}
is not a context-free language.
- Describe a general procedure for creating a CFG that captures
the Kleene star of a provided CFG.
- Deterministic contest-free languages (DCFLs) are not as powerful as
non-deterministic ones. Describe one reason why DCFLs are of interest
to the computer science community.
- Show a leftmost reduction of the string 1aaabbb using the
DCFG at the bottom of page 137.
Grading - 10 Points
- To earn points, your answers must be easily readable.
- You will earn 1 point per problem for a reasonable looking
solution.
- At least one problem will be selected for careful grading. The
rest of the 10 points will be allocated to these problems.
- Solutions to all problems will be posted.
Partners
You may work alone or you may partner with one classmate.
If you work with a partner, submit only one solution with
both of your names on it.
Submission
Upload your submission to the D2L Dropbox for Homework 4 no later
than 7:00 p.m. on Friday, March 4th. Late submissions receive
no credit, but partial credit can be earned by making an ontime
submission.
