Search code examples
grammarcontext-free-grammar

Find a grammar for the following language

Find a grammar for the following language:

  1. a*b | a

  2. (a*b | b*a)*

I think I have the answer for 1 (S -> aS | b) but I'm pretty confused on the second one. Any help would be greatly appreciated.

Solution

  • Language; (ab | ba)*

    S -> SA | epsilon

    A here represents (ab | ba)

    A -> B
A -> C

    B represents (a*b)

    B -> [Insert rule here]

    C represents (b*a)

    C -> [Insert rule here]