# 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 = {a
^{k} | 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.