Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Can someone help with this:

$L=\{a^ib^j \mid i,j \ge 0 \text{ and } i \ne 2j\}$

I'm trying to write a grammar for this language? I don't know how to do this. I tried this:
$S \rightarrow aaAb \mid aA \\ A \rightarrow aA \mid a$

share|improve this question
4  
You could simplify the task by splitting the language: $L = \{ a^i b^j \mid i < 2j \} \cup \{ a^i b^j \mid i > 2j \}$ –  Mike B. Feb 15 '13 at 11:55
3  
The reasoning being that CFG's are closed under union. –  Paresh Feb 15 '13 at 11:59
1  
Basically the question is already answered here: Context Free Grammar for language –  Hendrik Jan Feb 15 '13 at 19:15
add comment

2 Answers

up vote 4 down vote accepted

Consider the two languages:
$L_1 = \{a^ib^j \mid i, j \ge 0 \text{ and } i > 2j\}$
$L_2 = \{a^ib^j \mid i, j \ge 0 \text{ and } i < 2j\}$

Convince yourself that $L = L_1 \cup L_2$.

In $L_1$, the number of $a$'s are more than double of $b$'s, so there has to be atleast one $a$ (when there are no $b$'s). Also, for every addition of $b$, atleast 2 $a$'s must be added. You can generate $L_1$ as:

$ S_1 \rightarrow aA \\ A \rightarrow aaAb \mid aA \mid \varepsilon $

$L_2$ is a little more tricky. The number of $a$'s are less than double the number of $b$'s, so there can be $0$ $a$'s, but non-zero $b$'s. Consider the "base case" of $1$ $b$. The string can be either $b$ or $ab$. We will let the first rule generate this base case. After that, notice that for every addition of $b$, we can increase the number of $a$'s by at most $2$. So we can add $0$, $1$, or $2$ $a$'s for every addition of $b$. We'll let the second rule handle this. So, the CFG for $L_2$ becomes:

$ S_2 \rightarrow Bb \mid aBb \\ B \rightarrow Bb \mid aBb \mid aaBb \mid \varepsilon $

Note that CFG's are closed under union, that is, the union of two CFG's is also a CFG. So, to get the CFG for $L$, let the starting state $S$ of $L$ lead to either the starting state of $L_1$, or of $L_2$:

$S \rightarrow S_1 \mid S_2$

The rest of the rules remain the same as in the two languages. There may be a simpler grammar, but this was the first that came to mind.

share|improve this answer
add comment

Start with a grammar for $\{a^i b^{2 i} : i \ge 0\}$: $$ S \rightarrow a S bb \mid \epsilon $$ Now hack it so that there are more $a$ than $bb$: $$ \begin{align*} S &\rightarrow a S bb \mid A \\ A &\rightarrow a A \mid a \end{align*} $$ The modificaton to force more $b$ is similar, and left to you. It adds a nonterminal and three productions.

share|improve this answer
2  
This will not generate strings of all $a$'s or all $b$'s, which are a part of $L$. –  Paresh Feb 15 '13 at 13:49
    
If I change the question to i,j≥1 and i≠j and i<2j so how can i think of solution? –  user6885 Feb 15 '13 at 17:45
    
@Paresh, the part of extra $b$s is left to complete. And all $a$s is $S \Rightarrow A \Rightarrow^* a^k$. –  vonbrand Feb 15 '13 at 18:06
    
Aah ... I don't know how I missed that. Sorry! –  Paresh Feb 15 '13 at 18:11
    
@Vonbrand the problem that i dont know i to do the extra bso that it will not be more then the a. –  user6885 Feb 15 '13 at 20:13
show 1 more comment

Your Answer

 
discard

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.