Defining a grammar $G$ for the language $\mathcal L(G) = \{a^i b^j c^k \mid 0 \leq i < j < k\}$

71 Views Asked by At

I've run into some difficulties writing up a grammar $\newcommand{\perm}[1]{\left\langle #1 \right\rangle}G = \perm{\Sigma,V, P, S }$ for the language $\newcommand{\lang}{\mathcal{L}}$ mentioned in the title and repeated below for clarity: $$ \newcommand{\set}[1]{\left\{ #1 \right\}} \lang(G) = \set{ a^i b^j c^k \mid 0 \leq i < j < k } \,. $$ More specifically, I'm having trouble making the left and right ends of the words communicate with each other. The necessity for this should become obvious once one realizes the language has to be context sensitive: as the number of letters $a$ cannot reach the number of letters $b$, and the number of letters $b$ cannot reach the number of letters $c$, one cannot add the first two letters into the word without knowing the current state of the derivation in progress, a.k.a. the context.

The base case $a^0 b^1 c^2 = \epsilon b cc$ is fairly easy to construct. We define the following 3 productions $P$ to facilitate this: \begin{align} \newcommand{\rewrite}{\longrightarrow}\newcommand{\derive}{\Longrightarrow} % S &\rewrite \epsilon B C \tag{1}\label{eq:S->eBC} \\ % \epsilon B & \rewrite b \tag{2}\label{eq:eB->b} \\ % b C & \rewrite b cc \tag{3}\label{eq:bC->bcc} \end{align} This leads to the derivation $$ \newcommand{derive}{\Longrightarrow} S \overset{\eqref{eq:S->eBC}}{\derive}_G \epsilon B C \overset{\eqref{eq:eB->b}}{\derive}_G \epsilon b C \overset{\eqref{eq:bC->bcc}}{\derive}_G \epsilon b cc\,. $$ The next thing is to allow for the addition of the letters $a$ to the beginning of the word. We do this by adding the productions \begin{align} S &\rewrite ABC \tag{4}\label{eq:S->ABC} \\ A & \rewrite a \tag{5}\label{eq:A->a} \\ aB & \rewrite abb \tag{6}\label{eq:aB->abb} \\ bbC & \rewrite bbccc \tag{7}\label{eq:bbC->bbccc} \\ AB &\rewrite aAB \tag{8}\label{eq:AB->aAB} \end{align} to the mix. With this we can do the following: $$ S \overset{\eqref{eq:S->ABC}}{\derive}_G ABC \overset{\eqref{eq:A->a}}{\derive}_G aBC \overset{\eqref{eq:aB->abb}}{\derive}_G abbC \overset{\eqref{eq:bbC->bbccc}}{\derive}_G abbccc $$ and $$ S \overset{\eqref{eq:S->ABC}}{\derive}_G ABC \overset{\eqref{eq:AB->aAB}}{\derive}_G aABC \overset{\eqref{eq:AB->aAB}}{\derive}_G aaABC \overset{\eqref{eq:AB->aAB}}{\derive}_G \cdots $$

But this is when we run into our first two real problems: we would somehow need to be able to tell how many letters $a$ there are at the beginning of the word to be able to tell how many $b$s we should add (at the very least). This would have to be done recursively, as it is impossible to write a production for every case like this: \begin{align} aAB &\rewrite aABbb\\ aaAB &\rewrite aaABbbb \\ &\quad\vdots \end{align}

Also, I've manually added the necessary number of letters $c$ at the end of the derivation right after \eqref{eq:AB->aAB}, which is clearly not the way forward.

What might be a good approach to generating this grammar? My first hunch is that by modifying \eqref{eq:AB->aAB} a bit, like adding more $B$s and $C$s at the end might be productive, but I've not yet had the chance to try this. I could spend days on this thing, but I'd rather ask if the approach I've taken is any good in the first place rather than try to endlessly bash my head against the wall trying to find corner cases.

1

There are 1 best solutions below

1
On BEST ANSWER

A simpler problem would be to try to figure out how to generate the language $L = \{ a^n b^n c^n \mid n \geq 0\}$, since your language should be just modifying a couple of the rules. To generate $L$, we could start with some productions generating a balanced pairs language: $$ S \to D$$ $$ S \to a S X$$ Here $D$ stands for “done”, as in “we’re done with this step and we don’t want to use the two productions above anymore”. We get the balanced pairs language $\{ a^n D X^n \mid n \geq 0\}$. Now we have to do something with $D X^n$ to get to $b^n c^n$. What we could do is turn each $X$ into a $YZ$: $$ X \to YZ$$, Then allow the $Y$’s and $Z$’s to slide past each other: $$ YZ \to ZY$$ Now we make the $Z$’s turn into $c$’s once the hit the end of the word: $$ Z\epsilon \to c$$ $$ Z c \to cc$$ And likewise for the $b$’s: $$ D X \to b$$ $$ b X \to bb$$ And finally I think there is a problem with the empty string: $$ \epsilon D \epsilon \to \epsilon$$