Date Added: Jul 2012
A pushdown automata is one way finite automata with a separate pushdown store that is first in first - out storage structure, which is manipulating by pushing and popping. Probably, such machines are best known for capturing the family of context free languages, which was independently established by Chomsky (Cole 1971). Pushdown automata have been extended in various ways. The extension of pushdown automata is recently introduced, is called flip pushdown automata (Border et al 1982). A is an ordinary pushdown with the additional ability to flip its pushdown during the computation. This allows the machine to push and pop at both ends of the pushdown, therefore, a flip-pushdown is a form of a dequeue storage structure and it becomes an equally power to Turing machines.