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)
