Name: ____________________________________________________ Alpha: _____________________

## Problem 1

Run the mystery algorithm on the following grammar:
S → XSY | Z
X → ab
Y → ba
Z → bZ | a
Draw the result in JFLAP and test it on the string ababa. JFLAP will show you the sequence of configurations in the accepting computation. Turn In a screen capture of your machine.

## Problem 2

Draw the parse tree for ababa using the above grammar. Write down the sequence of configurations in an accepting computation for your machine on input ababa. Is there a connection between the parse tree and the sequence of configurations? Turn In your drawings and answer to the question.

## Problem 3

Consider the following grammar for add/subtract arithmetic.
S → S op x
S → x
... where op is thought of as standing for either + or -, and x for a number. Let's add subscripts to each S, op, and x to let us know what they stand for. So, "5 + 3" is represented by "x5 op+ x3". Now we can actually view a derivation as computation by providing rules for how the subscripts on symbols in the grammar relate to the rules:
 Sk → Si opf xj k = operator f applied to i and j Sk → xi k = i
With this, you can see how the parse tree for x op x op x, for example, gives an evaluation for an expression like 3 - 1 + 6.
Here is the machine produced by our grammar-to-PDA conversion algorithm:
Write down the sequence of configurations in an accepting computation by this machine on input
x5 op- x3 op- x1
but in your configurations write down each symbol with its subscript.
Example - input 2+5:
(q0,x2 op+ x5, λ) ⇒ (q1,x2 op+ x5, $) ⇒ (q1,op+ x5, x2$) ⇒ (q1,op+ x5, S2$) ⇒ (q1, x5, op+ S2$) ⇒ (q1, λ, x5 op+ S2$) ⇒ (q1, λ, S7$) ⇒ (q2, λ, λ)
Note: You should see how the highlighted "reduce" transitions, where we pop a rule left-hand-side (in reverse) and push a right-hand-side, update subscript values.
Turn In your sequence of configurations along with the answer to the following question: What just happened with the subscripts you generated?