[Solved]: Is the language $a^i b^j c^k$ with $i+j > k$ context-free?

Problem Detail: 

I am learning about Context Free Grammars and currently stuck on the following question.

Is the following language context-free? If not, then how can we prove it using Pumping Lemma?

$\qquad L = \{a^i b^j c^k \mid i,j,k \geq 0 \land i+j > k\}$.

After spending some time I have been able to generate the production rules for the following language, but unable to understand and conclude the above.

Important Condition ($i+j = k$)

$\qquad M = \{a^i b^j c^k \mid i,j,k \geq 0 \land i+j = k\}$.

$\qquad\begin{align*} S &\to aSc \mid X \\ X &\to bXc \mid ε \end{align*}$

Any assistance in solving the condition ($i+j > k$) would be a great help.

Asked By : Boring Loop

Answered By : Yuval Filmus

There is a simple way to obtain a grammar for the language $L_{\geq} = \{a^ib^jc^k : i+j \geq k\}$ given a grammar for the language $L_= = \{a^ib^jc^k : i+j = k\}$. Starting with a grammar for $L_=$, change all rules mentioning $c$ to rules mentioning a new non-terminal $C$, and add the two productions $C\to c \mid \epsilon$.

Concretely, if we start with the following grammar for $L_=$: $$ \begin{align*} &S\to aSc \mid T \\ &T\to bTc \mid \epsilon \end{align*} $$ then the corresponding grammar for $L_{\geq}$ is $$ \begin{align*} &S\to aSC \mid T \\ &T\to bTC \mid \epsilon \\ &C\to c \mid \epsilon \end{align*} $$

Of course, this is not quite the restriction we were after. It is possible to modify the grammar for $L_{\geq}$ to a grammar for $L_{>} = \{a^ib^jc^k : i+j > k\}$ by "signalling" within the grammar that at least one $c$ was actually dropped. This requires duplicating some of the non-terminals and rules. Details left to you.

Another modification which will produce $L_{\geq}$ from $L_=$ replaces each $a$ by a non-terminal that generates $a^+$, and each $b$ by a non-terminal that generates $b^+$: $$ \begin{align*} &S\to ASc \mid T \\ &T\to BTc \mid \epsilon \\ &A \to Aa \mid a \\ &B \to Bb \mid b \end{align*} $$ Again we can use signalling to get $L_>$ rather than $L_{\geq}$. Details left to you.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50598

3.2K people like this

 Download Related Notes/Documents