## A community for students. Sign up today

Here's the question you clicked on:

## seanwalsh1984 2 years ago 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.

• This Question is Closed
1. Tomas.A

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

2. Tomas.A

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

3. Tomas.A

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)

4. seanwalsh1984

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?

5. Tomas.A

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

6. seanwalsh1984

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

#### Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy