CSCI 338: Homework 3

Sample Solution

The problems selected for careful grading were #1 (part c was worth 2 points, part f was worth 1 point) and #6 (worth 3 points).

Problems - This homework set is complete

  1. Problem 2.4, parts (c) and (f) on page 155.
  2. Problem 2.6, part (b) on page 155.
  3. Problem 2.14 on page 156.
  4. Draw a picture of a pushdown automaton (using the style shown in Figure 2.15 on page 115) that recognizes the language described in Problem 2.6, part (b) on page 155.
  5. Consider the PDA in the preceding question. What is Q? What is Σ? What is Γ? What is q0? What is F? (You do not need to specify δ.)
  6. Convert the following CFG to an equivalent PDA, using the procedure given in Theorem 2.20:
       S → aSb | bY 
       Y →  Ya | ε

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 3 no later than 7:00 p.m. on Friday, February 26th. Late submissions receive no credit, but partial credit can be earned by making an ontime submission.

Valid XHTML 1.0!