Equivalent context free grammar for pushdown automata

[edit] This machine does not accept L = {a^(n)b^(n)c^(n) | n > 0} and instead accepts L = {a^(2n+1)b^(2n+1)c^(2n+1)}; also, as a side note please don't try to fix my machine - I want to do it. I have an idea.

[edit 2] This doesn't work and I don't think there is any fixing this - oh well.

So I'm kind of confused on this idea of pushdown automata and context free grammar being equivalent. For instance, in the language,

L = {a^(n)b^(n)c^(n) | n > 0},

we can design some pushdown automaton - we'll omit pushing and popping a start symbol from the stack for the sake of brevity.

The Machine

Say we have a state q1 that reads every 'a' present in the string and simultaneously pushes an 'a' to the stack whilst looping on itself - to get from q1 to, say q2, we read a 'b' from the string, pop 'a', and push nothing. Next we have q2, q2 has two different transfers that it can go to: q3 or q4. to get to q3, we read 'b', pop nothing, and push nothing - q3 has one transfer that goes to q2; this transfer is as follows: we read 'b', pop 'a', and push nothing. To get to q4 we read 'c', pop 'a', and push nothing. At q4 we can go to q5: To get to q5, we read c, pop nothing, and push nothing. q5 has a transfer back to q4 - the transfer is as follows: we read a 'c', pop an 'a', and push nothing. The stack, given a valid string, will be completely empty at the end of this process - thus the string is accepted.

My question

A context free grammar cannot create this language; this makes me question the scope of pushdown automaton; I thought pushdown automata and context free grammars were equivalent - especially given the fact that this pushdown automaton is deterministic.

Comments and answers would be very much appreciated!
Kyle (Hiefenhoomer)

  • $\begingroup$ How did your machine guarantees that the numbers of $a$, $b$, and $c$ are equal? $\endgroup$
    – Russel
    May 2 at 2:30
  • $\begingroup$ @Russel Lol I just realized this only works for a^(2n+1)b^(2n+1)c^(2n+1). I'm sure this PDA can be altered to fix this. I'll answer you later I promise! I just have to study for finals. $\endgroup$ May 2 at 2:57
  • $\begingroup$ The language is not context-free and I think you already covered in your class that CFG and PDA are equivalent. Hence if something is not possible in one form, it is not possible in the other. $\endgroup$
    – Russel
    May 2 at 3:02
  • $\begingroup$ Ok, so what I've learned is the fact that I'm a silly goose - thanks for pointing this out. I've tried to figure this out a little and it's not working. $\endgroup$ May 2 at 3:56
  • $\begingroup$ You argued the language $L$ of the regular expression is part of the machine's language - say $M$. Is $M \subset L$? $\endgroup$
    – greybeard
    May 2 at 5:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.