1
$\begingroup$

How do I generate a context free grammar for a language

$$\left\{a^ib^jc^k:i=j\text{ or }j=k,\text{ and }i,j,k\ge 0\right\}\;?$$

Thanks.

$\endgroup$
  • $\begingroup$ Please read this post and the others there for information on writing a good question for this site. In particular, people will be more willing to help if you edit your question to include some motivation, and an explanation of your own attempts. $\endgroup$ – Daniel R Oct 9 '13 at 6:29
1
$\begingroup$

HINT: Write separate context-free grammars for

$$L_1=\left\{a^ib^jc^k:i=j\text{ and }i,j,k\ge 0\right\}$$

and

$$L_2=\left\{a^ib^jc^k:j=k\text{ and }i,j,k\ge 0\right\}\;,$$

making sure to use disjoint sets of non-terminal symbols. If the initial symbols of these grammars are $S_1$ and $S_2$, combine them by adding a new initial symbol $S$ and the productions $S\to S_1\mid S_2$.

Grammars for $L_1$ and $L_2$ are pretty straightforward, if you’ve seen a grammar for $$\{a^nb^n:n\ge 0\}\;;$$ it’s a standard example, so you probably have.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.