Context-free grammar for a language

0
votes

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.

1
compiler-constructionlanguage-designcomputation-theory
You might want to also post this to cstheory.stackexchange.com if you haven't already. – MatthewMartin
@Matthew: cstheory is for research-level questions. – sepp2k

1 Answers

1
votes

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