0
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
user2943731
Posted 2017-11-11T22:08:23.860
Reputation: 23
1
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.
Hendrik Jan
Posted 2017-11-11T22:08:23.860
Reputation: 24 682
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. – user2943731 – 2017-11-13T21:13:57.060
1Your language is not context free. – Yuval Filmus – 2017-11-11T22:15:34.013
2
Possible duplicate of How to prove that a language is not context-free?
– David Richerby – 2017-11-12T00:36:52.417The 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!
– Raphael – 2017-11-12T21:09:17.627I 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? – Raphael – 2017-11-12T21:11:03.597