CSCI 338: Homework 4

Sample Solution

The problems selected for careful grading were #2 (3 points) and #3 (4 points).

Problems - This homework set is complete

  1. Problem 2.30, part (a) on page 157.
  2. Prove that language P = {ak | k is a prime number} is not a context-free language.
  3. Describe a general procedure for creating a CFG that captures the Kleene star of a provided CFG.
  4. 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.
  5. Show a leftmost reduction of the string 1aaabbb using the DCFG at the bottom of page 137.

Grading - 10 Points


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.


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.

Valid XHTML 1.0!