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 "x_{5} op_{+} x_{3}". 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.
S_{k} → S_{i} op_{f} x_{j} k = operator f applied to i and j S_{k} → x_{i} 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
x_{5} op_{-} x_{3} op_{-} x_{1}but 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,x_{2} op_{+} x_{5}, λ) ⇒ (q1,x_{2} op_{+} x_{5}, $) ⇒ (q1,op_{+} x_{5}, x_{2}$) ⇒ (q1,op_{+} x_{5}, S_{2}$) ⇒ (q1, x_{5}, op_{+} S_{2}$) ⇒ (q1, λ, x_{5} op_{+} S_{2}$) ⇒ (q1, λ, S_{7}$) ⇒ (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.