Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|cite|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|cite|improve this 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$.

share|cite|improve this answer

Your Answer


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.