Name: ____________________________________________________ Alpha: _____________________
Describe help received: _________________________________________________________________
S → XSY | ZDraw 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.
X → ab
Y → ba
Z → bZ | a
S → S op 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:
S → x
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.
Sk → Si opf xj k = operator f applied to i and j Sk → xi k = i
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- x1but in your configurations write down each symbol with its subscript.
Example - input 2+5:Turn In your sequence of configurations along with the answer to the following question: What just happened with the subscripts you generated?
(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.