Prove that the syntax is equivalent

Question

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

Answer 1

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.