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 "x₅ op₊ x₃". 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

x₅ op_- x₃ op_- x₁

but in your configurations write down each symbol with its subscript.

Example - input 2+5:
(q0,x₂ op₊ x₅, λ) ⇒ (q1,x₂ op₊ x₅, $) ⇒ (q1,op₊ x₅, x₂$) ⇒ (q1,op₊ x₅, S₂$) ⇒ (q1, x₅, op₊ S₂$) ⇒ (q1, λ, x₅ op₊ S₂$) ⇒ (q1, λ, S₇$) ⇒ (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?