# Prove that the syntax is equivalent

I don't "see" why the following syntax is equivalent to the second

syntax1:

E -> E + T
E -> T


syntax2:

E -> T E'
E' -> + T E'
E' ->


(it is to avoid left recursion and I am not understanding why the solution works)

How do I mathematically prove that both syntax definitions are equivalent

An intuitive approach towards the difference is understanding that the productions of syntax #1 add new material to the left of existing symbols whereas those of syntax #2 do so on the right-hand side.

• syntax #1:

derived string of terminals:   T    + T   + T  ...  + T   + T 
derivation step:             [ n ] [n-1] [n-2]     [ 2 ] [ 1 ]

• syntax #2 (step #n is the application of rule 3 and produces no terminal) :

derived string of terminals:   T    + T   + T  ...  + T   + T 
derivation step:             [ 1 ] [ 2 ] [ 3 ]     [n-2] [n-1]


for a rigorous proof note that under both syntaxes, each derivation leads to an initial T followed by sequence of + T. for the grammars at hand this can be proven by induction over the number of rule applications.