Search code examples
compiler-constructionlanguage-designcomputation-theory

Context-free grammar for a language

I have a problem with the following language:

alt text

I must write a context-free grammar:

alt text

which describes it. I have already done a few exercises but this one is really hard for me.I'm sitting around for hours without an useful approach. It wouldn't be a problem to write a grammar without the part N0: (m=l) v (l = 2n) . But i don't how to get this one done. I would be very thankful for any advice.

Solution

  • I'm not sure about the syntax for G2 but the following CFG works:

    S = S1 | S2

S1 = S11 C
S11 = <empty> | a S11 b
C = <empty> | c C

S2 = aa S2 c | B
B = <empty> | b B