1

I'm trying to construct a grammar for the following language $$L=\{a^ib^jc^i,\ i,j\ge 0\}$$

My try:

$$G=\left(V=\{S,X,Y\},\Sigma=\{a,b,c\},R,S\right)$$ where the rules are \begin{align*}S&\to X|Y \\ X&\to aXc|Y\\Y&\to bY|\varepsilon\end{align*} Is it good?

Any feedback/help would be appreciated, thank you!

Galc127
  • 4,451

1 Answers1

1

Yes, it’s correct. You can demonstrate this informally as follows. First notice that $Y$ generates $L_0=\{b^n:n\ge 0\}$. Thus, the production $S\to Y$ picks up all of $L_0$. If instead we start with $S\to X$ and then apply $X\to aXc$ $m$ times followed by $X\to Y$, we have $a^mYc^m$, which we already know generates $\{a^mb^na^m:n\ge 0\}$. Thus, altogether we get

$$L_0\cup\bigcup_{m\ge 1}\{a^mb^na^m:n\ge 0\}=L\;,$$

as desired.

Brian M. Scott
  • 616,228