Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Construct a grammar $G$ such that $$L(G) = \{ a^nb^m|n \neq 2m,m,n \ge 0\}$$

My attempt:

I first constructed a grammar for the langugage $L(G_1) = \{ a^nb^m|n = 2m,m,n \ge = 0\}$,

$G_1 = (\{ S\}, \{a,b\},P,S) $ where $P$ consists of $S\to aaSb|\lambda$

For violating this condition, I modified the above as $G = (\{ S,A,B\}, \{a,b\},P,S) $ where $P$ consists of $$S\to aaSb|A, A\to aBb, B\to aB|bB|\lambda$$ My question is this correct? If not where exactly I am going wrong?

share|cite|improve this question
up vote 1 down vote accepted

Your grammar \begin{align} S &\to aSbb \mid A \\ A &\to aBb \mid A \\ B &\to aB \mid \lambda \end{align} does not work because of two issues. First, did you mean $\{a^{2m}b^{m}\}$ or $\{a^{n}b^{2n}\}$? Second thing is that in your grammar $\#b \leq 2\cdot\#a$, but $L$ should include words like $b^{123}$. What you could do is split the grammar into two:

$$L_1 = \{a^nb^m\mid n > 2m \geq 0\},$$ $$L_2 = \{a^nb^m\mid 0 \leq n < 2m\}.$$

Then $G_1$ would be \begin{align} S_1 &\to aaS_1b \mid A, \\ A &\to aA \mid a, \end{align}

and $G_2$ \begin{align} S_2 &\to aaS_2b \mid aB \mid B, \\ B &\to bB \mid b. \end{align}

Some other (maybe more intuitive) $S_2$ could look like:

\begin{align} S_2 &\to AAS_2b \mid Ab,\\ A &\to a \mid \lambda. \end{align}

Hope this helps ;-)

Edit 1: I see that you fixed your grammar, but now you can create words like $ba$ which should not be in the language.

Edit 2: Expanded abbreviations into proper CFG and added second version of $S_2$.

share|cite|improve this answer
Thanks, but could you please explain what does $b^+,ab^+,a^+b$ means? – Quixotic Feb 4 '13 at 14:36
It's a regular expression, a shorthand for $B$ where $B \to bB \mid b$. – dtldarek Feb 4 '13 at 14:37
So do you mean: $S_1 \to aaS_1b \mid aBb \mid aB$? – Quixotic Feb 4 '13 at 14:39
I expanded the grammar, it should be more clear now. – dtldarek Feb 4 '13 at 14:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.