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

7.1k Views Asked by At

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?

1

There are 1 best solutions below

4
On BEST ANSWER

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$.