# CSCI 338: Homework 3

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

- Problem 2.4, parts (c) and (f) on page 155.
- Problem 2.6, part (b) on page 155.
- Problem 2.14 on page 156.
- 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.
- Consider the PDA in the preceding question. What is Q?
What is Σ? What is Γ? What is q
_{0}?
What is F? (You do not need to specify δ.)
- 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.