I am stuck on a question. Lets say there is a string that can be created from three alphabets a,b,c the condition is number of a<= number of b<= number of c. I can solve if there are a and b (two alphabets) but I am not able to solve for 3. Any help will be appreciated. Thanks

  • 1
    $\begingroup$ Your language is not context free. $\endgroup$ – Yuval Filmus Nov 11 '17 at 22:15
  • 2
    $\begingroup$ Possible duplicate of How to prove that a language is not context-free? $\endgroup$ – David Richerby Nov 12 '17 at 0:36
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Nov 12 '17 at 21:09
  • $\begingroup$ I have a hard time to find even a question here. People have been guessing you're trying to ask for a PDA for the given language. Is that what you want? $\endgroup$ – Raphael Nov 12 '17 at 21:11

The basic problem here is that context-free languages are not closed under intersection.

The example you give illustrates this. Thus, $\{ w\in\{a,b,c\}^* \mid |w|_a \le |w|_b\}$ is context-free, and similarly, so is $\{ w\in\{a,b,c\}^* \mid |w|_b \le |w|_c\}$. The intersection of these two languages $\{ w\in\{a,b,c\}^* \mid |w|_a \le |w|_b \le |w|_c\}$ is not context-free.

| cite | improve this answer | |
  • $\begingroup$ So that is the reason I was not able to come up with a PDA for this. I had been trying for so long every time something or the other will not work. Thanks a lot for clarifying this. $\endgroup$ – user2943731 Nov 13 '17 at 21:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.