Let Sigma = {a,b,c} and let L be the language of all words in which all the a’s come before the b’s and there are the same number of a’s as b’s and arbitrarily many c’s that can be in front, behind, or among the a’s and b’s. Some words in L are , abc, caabcb, ccacaabcccbccbc.

How can I solve this problem by empty stack model? My solution is that we push A for each 'a' and pop B for each 'b'. But how can we pop out all of 'c'? Can anyone give me some idea please?


For CF languages I really like to construct the grammar first. For $a^nb^n$ of course it is easy to construct a grammar:

$ S \rightarrow a S b \\ S \rightarrow \varepsilon $

Notice how it enforces the same amount of letters: A substitution of S generates an a in the front and a b in the back. Now what we need is to sprinkle in some c terminals among these. We can just use a rule like so:

$ X \rightarrow XX \\ X \rightarrow c \\ X \rightarrow \varepsilon $

This essentially generates an arbitrary amount of c terminals. Now all we need to do is to add it to S:

$ S \rightarrow XSX \\ S \rightarrow aSb \\ S \rightarrow \varepsilon $

From a CF grammar of course you can construct a PDA.


If you need to think about PDAs "directly", then construct the PDA for $a^nb^n$, but allow consuming c terminals in every state without modifying the stack.

  • $\begingroup$ But the requirement don't accept the converting from CFG to PDA. That's why I need the idea to do the PDA directly $\endgroup$
    – Thomas
    May 8 at 5:14
  • $\begingroup$ thanks a lot. I didn't know that we can consume a symbol without modifying the stack. Now it easier for me once I knew it. $\endgroup$
    – Thomas
    May 8 at 5:40
  • $\begingroup$ @Thomas This really depends on what construction you allow. If you "need to" modify the stack each step, then you can essentially take out and put back the same symbol. Non-modifying transitions are really just a syntactic sugar for taking out and putting back the same symbol for each element in our alphabet. $\endgroup$ May 8 at 5:48
  • $\begingroup$ I have another confusing not relate to this question. In case I need to create a language that accept odd length. What should I do? Specifically, w = {0,1}* | the length of w is odd and its middle symbol is 0. My idea for this question is that I'll push 1A for any 0 or 1 until it reach the "0" in middle then pop out all of the rest character. But how the language know which 0 is in the middle? $\endgroup$
    – Thomas
    May 8 at 5:54
  • $\begingroup$ @Thomas This site has a one question per post as well as no extended discussion in comments. I'd suggest continuing the discussion in the chat. $\endgroup$ May 8 at 6:00

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.