# Give a context-free grammar to generate the following language $L = \{ a^ib^jc^k \space|\space 0 \leq i \leq j \leq i + k \}$

Mathematics,

I'm studying for a final that I have, and I need help with a problem.

Give a context-free grammar to generate the following language $L = \{ a^ib^jc^k \space|\space 0 \leq i \leq j \leq i + k \}$

What does $0 \leq i \leq j \leq i + k$ mean I should do in terms of creating the grammar? Does it mean the number of a's must be less than (or equal to) the number of b's, and the number of b's must be less than or equal to the number of a's and c's combined?

If so, here is my attempt.

$G = ({S, A, B, T, E},{a, b, c},{S, R})$

$S \rightarrow AB \\ A \rightarrow B \\ A \rightarrow aB \\ A \rightarrow a \\ B \rightarrow bB \\ B \rightarrow AB \\ B \rightarrow bbT \\ T \rightarrow cT \\ T \rightarrow cE \\ E \rightarrow \epsilon$

Is this correct? If so, can it be reduced to fewer rules?

Edit: I think I overthought it. Here's another try:

$G = ((S, T), (a, b, \epsilon), S, R)$

where $R$ contains the rules:

$S \rightarrow cSb \\ S \rightarrow T \\ T \rightarrow cTa \\ T \rightarrow \epsilon \\$

I believe this is correct, but it wouldn't hurt for a member to look at my answer.

Third attempt: $S \rightarrow AB \\ A \rightarrow aAb \\ B \rightarrow Bc \\ B \rightarrow bBc \\ A \rightarrow \epsilon \\ B \rightarrow \epsilon$

-
Currently two of your exponents are i. I assume one of them should be a j. –  user18297 Dec 8 '12 at 5:03
@user18297 You're right, thank you. Fixed it. –  Grace C Dec 8 '12 at 5:23
Your new grammar appears to construct the language $\{ c^{i+j} a^j b^i : i, j \geq 0 \}$. –  Arthur Fischer Dec 8 '12 at 5:36
In order to get the curly braces in $\{x:\varphi(x)\}$, use \{ and \}. –  Brian M. Scott Dec 8 '12 at 7:18

Just as with computer programming, it’s a good idea to run some test derivations. Your first grammar permits the derivation of $bbcbbb$ via

$$S\to AB\to BB\to bbTB\to bbcTB\to bbcB\to bbcbB\to bbcbbbT\to bbcbbb\;,$$

but $bbcbbb\notin L$.

Your second grammar generates $\{c^ia^jb^k:i=j+k\}$, which wouldn’t be $L$ even if the $c$’s were on the right, because you have $i=j+k$ instead of $i\ge j+k$ and because you can have $j>k$. Part of the problem is that you started by generating the $b$’s and $c$’s; try starting with the $a$’s and $b$’s and using Arthur Fischer’s hint in his answer.

-
How about the third attempt? –  Grace C Dec 12 '12 at 2:01
@LearningPython: That appears to work. You could also replace your third production by $B\to C$ and make $C$ do nothing but produce $c$’s. –  Brian M. Scott Dec 12 '12 at 2:06
Ok, thank you very much! –  Grace C Dec 12 '12 at 2:08
@LearningPython: My pleasure! –  Brian M. Scott Dec 12 '12 at 2:08

Hint: Note that every string in your language can be expressed as $uv$ where $u \in \{ a^ib^i : i \geq 0 \}$ and $v \in \{ b^j c^k : 0 \leq j \leq k \}$ (and all such strings belong to your language).

-
Ok, how about the third attempt? –  Grace C Dec 12 '12 at 1:55
@LearningPython: As Brian has already said, it looks perfect (and it is actually the same grammar I would have come up with). –  Arthur Fischer Dec 12 '12 at 4:49