Let the input alphabet be $\Sigma = \{a,b,c\}$ and L be the language of all words in which all of the a’s come before all of 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 ccacaabcccbccbc

I know that the language is not regular but how can I find a deterministic PDA (in a drawing fashion) that accepts L?

Edit: So far I've ended up with this which takes care of having the same number of a's as b's and all a's come before all b's. However I cannot figure out how to account for the arbitrary amount of c's in-between b's. Any ideas? enter image description here

Sorry for the horrible drawing in advance.

  • $\begingroup$ @Bartek, how do you change the input alphabet to look like that? $\endgroup$
    – user3115
    Oct 22 '12 at 20:39
  • $\begingroup$ Using LaTeX syntax. You look for tips in Markup Editing Help $\endgroup$ Oct 22 '12 at 20:46
  • 1
    $\begingroup$ Ah. I think I can read your PDA "dialect". In read 2, when there is a c read, return to the x edge just before the read. That ignores the c, ready for the next letter. $\endgroup$ Oct 23 '12 at 8:36
  • $\begingroup$ If that is easier for you, you can come up with a grammar and convert it into an automaton with the canonical algorithm $\endgroup$
    – Raphael
    Oct 23 '12 at 9:10
  • $\begingroup$ @hendrik, ahh that's how we get the c's. Thanks for that, seems to work perfect now! $\endgroup$
    – user3115
    Oct 23 '12 at 19:32

Recipe in shorthand. Ignore $c$'s. Use a bottom fo stack symbol $Z$ that stays there. Keep the surplus of $a$'s on the stack. So $ZAAA$ (top of stack right) means three $a$'s more than $b$'s. If we read another $a$ push $A$, if we read another $b$ pop an $A$ (and move to another state to indicate we have now seen $b$).

  • $\begingroup$ Thanks for the reply, Im not really following your answer though. What would the PDA look like? $\endgroup$
    – user3115
    Oct 22 '12 at 21:16
  • $\begingroup$ I have tried to formulate this as hint, as many homework questions are posed here. With the suggested approach you can build the machine. Push $A$ when reading $a$ while there are $A$'s on the stack would be the instruction $(q,a,A,q,AA)$ in the usual PDA dialect. You work with the hint, or need all instructions? $\endgroup$ Oct 22 '12 at 21:24
  • $\begingroup$ Hmmm, Im not familiar with that dialect you mentioned, Iv'e just always used a drawing $\endgroup$
    – user3115
    Oct 22 '12 at 22:41
  • $\begingroup$ This is a loop on state $q$ that reads $a$, takes $A$ from top-of-stack, replacing it by $AA$. But the way the machine works is independent of how it is denoted (or drawn). $\endgroup$ Oct 22 '12 at 22:55
  • 2
    $\begingroup$ Perhaps it might help to think of this language as $a^{n}b^{n}$ with a bunch of $c$'s stuck wherever (so you can just read the $c$'s without pushing or popping anything). $\endgroup$ Oct 23 '12 at 0:49

Your diagram looks like you have the correct answer. Just for comparison:enter image description here

Somewhat overannotated, but I don't think I've missed anything. As best I can tell, your diagram expresses the same idea.

  • $\begingroup$ ahh.. missed the answer by 5 min !! $\endgroup$
    – bongubj
    Oct 23 '12 at 7:10
  • $\begingroup$ Always the way ;) $\endgroup$ Oct 23 '12 at 8:59

Perhaps this diagram will explain in a clear mannerenter image description here

Simply put,

When you start, put a $ symbol as starting marker. Now, if you see c dont do anything.

If you see a put a symbol into your stack. Go on doing this till you see b. 

Once you see b pop out the a symbol from the stack. (just like before if you see c dont do anything). 

Once you reach the end of input, see if the stack is empty (by checking our $ marker). If yes, accept the string. Else reject.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy