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 \}$

Question

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$

Answer 1

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.

Answer 2

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