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 q₀? 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

• 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 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.