Preview CFG: Many axb

  • Grammar:
    • 1 production per line
    • start nonterminal: left-hand side of first production
    • Remove: Right click on state ➞ 'Remove'
  • Productions:
    • form: S -> X Y | a S b | \eps
    • left-hand side: a single nonterminal
    • right-hand side: groups of nonterminals and terminals separated by "|"
  • Nonterminals:
    • form: one single upper case character A-Z
  • Terminals:
    • allowed: abcdefghijklmnopqrstuvwxyz()[]{}
  • Empty word::
    • empty word: ε (write \epsilon or \eps or \e)

Problem

For the following grammar G with the productions:

S → a S b | x | S S

Give a CNF G' such that L(G') = L(G)\ ε.

(remember: CNF allows only productions with the form "X -> Y Z" or "X -> a")