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

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?

Attempt 1. If so, here is my attempt. $G = ({S, A, B, T, E},{a, b, c},{S, R})$, where \begin{align} 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 \end{align}

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

Attempt 2. I think I overthought it. Here's another try: $G = ((S, T), (a, b, \epsilon), S, R)$ where $R$ contains the rules: \begin{align} S &\rightarrow cSb \\ S &\rightarrow T \\ T &\rightarrow cTa \\ T &\rightarrow \epsilon \end{align}

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

Attempt 3. Consider the following rules: \begin{align} S &\rightarrow AB \\ A &\rightarrow aAb \\ B &\rightarrow Bc \\ B &\rightarrow bBc \\ A &\rightarrow \epsilon \\ B &\rightarrow \epsilon \end{align}

-

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

Let us first consider the following two languages:

• $L_1 = \{ \mathtt{a}^i \mathtt{b}^i : i \geq 0 \}$; and
• $L_2 = \{ \mathtt{b}^j \mathtt{c}^k : 0 \leq j \leq k \}$.

It can be shown that the language $L$ is actually the same as $$\{ uv : u \in L_1, v \in L_2 \},$$ and so we can reduce the problem to finding context-free grammars for the languages $L_1$ and $L_2$ as follows:

Suppose that $G_1$ is a CFG for $L_1$ with starting symbol $S_1$, and $G_2$ is a CFG for $L_2$ with starting symbol $S_2$. Further assume that no nonterminal symbol is a symbol in both $G_1$ and $G_2$. We construct a CFG for $L$ with new starting symbol $S$ as follows:

• $S \rightarrow S_1 S_2$
• $\left\{ \begin{array}{c}\text{all the}\\ \text{rules in} \\ G_1 \end{array}\right.$
• $\left\{ \begin{array}{c}\text{all the}\\ \text{rules in} \\ G_2 \end{array}\right.$

It should be fairly straightforward to construct context-free grammars for the languages $L_1$ and $L_2$.

-