S => ABA | AB | BA | AA | A | B - A => aA | b - B => bB | b -

• A CFG G = (V, T, R, S) is said to be in GNF if every production is of the form

  A → aα, where a ∈ T and α ∈ V∗

  i.e., α is a string of zero or more variables.

• Definition: A production U ∈ R is said …