2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ As you are comfortable with equality, would you be able to solve {a^i b^j d^l c^k | i+j = l+k}? Doesn't that help to solve your problem? $\endgroup$ – AProgrammer Dec 11 '15 at 11:01
  • $\begingroup$ How does it solve my problem? I don't even know if the above grammar is Context Free. If context free, then I would need production rules and I cannot think of one. If Not context free, then I would need pumping lemma to prove that it is not CFG. I am just learning. :) $\endgroup$ – Boring Loop Dec 11 '15 at 11:10
  • 1
    $\begingroup$ How does it solve my problem? It does not solve your problem, it should help you to find a solution to your problem. Your problem has two aspects, my intermediate question allows to think about them separately which should be easier. $\endgroup$ – AProgrammer Dec 11 '15 at 11:21
  • $\begingroup$ Another hint: Consider how in the equality case, you produce pairs of ($a$ or $b$)s and $c$s to enforce the constraint. Now you want fewer $c$s, i.e. you need to stop adding them at some point. $\endgroup$ – Klaus Draeger Dec 11 '15 at 12:44
  • 1
    $\begingroup$ 1) We don't do homework-solving or homework-grading (no matter if you are learning on your own or in a course) but instead expect you do work off the provided hints. 2) You need to be more careful about the difference between languages and grammars. 3) Note that you can use MathJax; I edited some formulae to use it, you can apply it to the rest of your post. $\endgroup$ – Raphael Dec 11 '15 at 13:38
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by 'signaling'? $\endgroup$ – Boring Loop Dec 11 '15 at 17:55
  • $\begingroup$ You'll figure out if you follow the route I suggest. (Which might not be the most direct one, by the way.) It's not standard terminology. $\endgroup$ – Yuval Filmus Dec 11 '15 at 18:55
2
$\begingroup$

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*} $$

$\endgroup$
  • 2
    $\begingroup$ Seems OK. You should try to explain why you think this works. $\endgroup$ – Yuval Filmus Dec 11 '15 at 21:55
0
$\begingroup$

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

$\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.