View source for Notes:Possible error 2016 compiler design q2b

__TOC__
==Question==
[[File:Cs3250-2016-with-solutions.pdf]] - question 2 part b - which can be found on the front page
==Examiner's answer==
The same as mine, but with a transition via {{M|y}} from my {{M|A_5}} to {{M|G_2}}, see bottom of page 5 in [[File:Cs3250-2016-with-solutions.pdf]]
==Alec's answer==
{| class="wikitable" border="1"
|-
! #
! Production
! DFA
! Comment
|-
! 0
| {{M|S::\eq\ A\#}}
| rowspan="6" | <m>\begin{xy}\xymatrix{& & & *++[o][F=]{C_0}  
\\ \text{start} \ar[r] & *++[o][F=]{A_5} \ar[dr]^B \ar[ddr]_x \ar[r]^A \ar & *++[o][F-]{B} \ar[ur]^{\#} \ar[r]^z \ar[dr]^x & *++[o][F=]{D_1} 
\\ & & *++[o][F-]{F} \ar[dr]_y & *++[o][F=]{E_3}
\\ & & *++[o][F-]{H} \ar[dr]_y & *++[o][F=]{G_2}
\\ & & & *++[o][F=]{I_4}   }\end{xy} </m>
| rowspan="6" | Notice that if we just have the input "{{M|y}}" we are stuck on {{M|A_5}}, this is accepting so we "construct" (reduce {{M|\epsilon}} - nothing - to {{M|B}}) {{M|B}} from an {{M|\epsilon}} and go back to the start. 

We now have a {{M|B}} on the top of the stack, we shift this and end up at state {{M|F}}, we shift the next top-of-the-stack (the {{M|y}} from before) ending up at {{M|G_2}}, this is an accepting state, so:
* We reduce the {{M|y}} and {{M|B}} on the top of the stack to an {{M|A}} - as per production {{M|2}}
* Go back to the start (ie {{M|A_5}})

We then shift the {{M|A}} and shit the {{M|\#}} (assuming this means "end of input") then reduce both to the start symbol, which is the accept-the-parse of accepting states, we're done.

There is some abuse of terminology here, but you see what I mean, and we'd usually use numbers for the states. 

Regardless we reduce to "logically" get a {{M|B}} from {{M|\epsilon}}, shift the {{M|y}} over that, reduce them both to get an {{M|A}}, shift the {{M|\#}} over that, reduce them both to get an {{M|S}}, we're done.
|-
! 1
| {{M|A::\eq\ Az}}
|-
! 2
| {{M|A::\eq\ By}}
|-
! 3
| {{M|B::\eq\ Ax}}
|-
! 4
| {{M|B::\eq\ xy}}
|-
! 5
| {{M|B::\eq\ \epsilon}}
|}