Question

Let the alphabet = {a, b}. Part (a): Give a Context Free Grammar for the language {a^nb^m | n > 2m}.

I have NO clue at all.

Answer 1

if zero b's then there must be at least one a
if one b then there must be at least three a's
if two b's then tehre must be at least five a's
and so on

Answer 2

also first should come a's and only then b's

Answer 3

so we start with
S -> aQT (we must have at least one a)
Q -> aQ | ε (we can generate any number of a's before b)
T -> aaTb | ε (if we create at least one b we must put two a's before b)

Answer 4

Wow! Thanks! Here is what I came up with this morning toying around.
\[S_0 \rightarrow aaS_1b | aaS_1b | aS_1\]
\[S_1 \rightarrow S_0\epsilon | a\]

Is this equivalent?

Answer 5

no, for example you can't get just a, but according to rules you should be able to
however maybe you made mistake by typing because if it will be
S_1 -> S_0|ϵ|a
i think it would be ok

and aaS_1b is same as aaS_1b so why you mention it 2 times? :D

Answer 6

Yes you are right, I mistyped, and my computer was acting up. I did have S1->S0 | epsilon | a.
Thanks for the help!