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

Question

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.

Answer 1

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.

Answer 2

I think self-learning along with the assistance of you all has really helped. Thank you for all your help.

Please input or comment, if the below production rules can be edited or modified into something more succinct. I think it can be improved

The following Language is Context-Free

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

Production Rules

$$ \begin{align*} &S\to aAE \mid AU \\ &A\to aA \mid \epsilon \\ &B\to bB \mid \epsilon \\ &E\to aEc \mid F \\ &F\to bFc \mid \epsilon \\ &U\to aUc \mid V \\ &V\to bVc \mid bB \\ \end{align*} $$

Strings Generated

$$ \begin{align*} &a \mid b \\ &bb \mid ab \mid aa \\ &aac \mid bbb \mid abb \mid abc \mid abc \mid aaa \mid bbc \\ &abbc \mid aaac \mid abbc \mid bbbc \mid aabc \mid aabc \\ &abbcc \mid bbbcc \mid aaacc \mid abacc \mid abacc \mid abbcc \\ &abbbccc \mid aabbccc \mid aaaaccc \mid aaabccc \\ &aabbbbbbbccccccc \mid aabbbbbbbcccccccc \end{align*} $$

Answer 3

Yes, above language is context free. You can design Pushdown automata for above language easily.

I'll describe pushdown automata function intuitively -> Start pushing all a's if there are any. Once all a's are finished, then start pushing b's if any. Then starting popping one symbol off stack for each c. At then end of you see end of input & stack is non empty you accept. (I'm not describing the process of rejecting input if it is not in format of a^ib^jc^k, format , as I think it is intuitive).

As far as grammar is involved you have to write grammar similar to what you have written , you just need to do few modifications.

i+j > k, Due to think condition minimum strings of above Context Free Language are a or b. Now S corresponds to state which can generate any no of a's. Y can generate any no of b's. aS and bY help in generating more no of a's/b's than c's. Just a or just b are terminating condition, see that you can generate any string from this grammar.

S -> aSc | aS | a | Y

Y -> bYc | bY | b