an equivalent nondeterministic pushdown automaton. The derivation process of the grammar is simulated in a leftmost way. Where the grammar rewrites a nonterminal, the PDA takes the topmost nonterminal from its stack and replaces it by the right-hand part of a grammatical rule (expand). Where the grammar generates a terminal symbol, the PDA reads a symbol from input when it is the topmost symbol on the stack (match). In a sense the stack of the PDA contains the unprocessed data of the grammar, corresponding to a pre-order traversal of a derivation tree. Technically, given a context-free grammar, the PDA has a single state, 1, and its transition relation is constructed as follows. for each rule (expand) for each terminal symbol (match) The PDA accepts by empty stack. Its initial stack symbol is the grammar's start symbol. For a context-free grammar in Greibach normal form, defining (1,γ) ∈ δ(1,a,A) for each grammar rule A → aγ also yields an equivalent nondeterministic pushdown automaton. The converse, finding a grammar for a given PDA, is not that easy. The trick is to code two states of the PDA into the nonterminals of the grammar. Theorem. For each pushdown automaton one may construct a context-free grammar such that The language of strings accepted by a deterministic pushdown automaton (DPDA) is called a deterministic context-free language. Not all context-free languages are deterministic. As a consequence, the DPDA is a strictly weaker variant of the PDA. Even for regular languages, there is a size explosion problem: for any recursive function and for arbitrarily large integers , there is a PDA of size describing a regular language whose smallest DPDA has at least states. For many non-regular PDAs, any equivalent DPDA would require an unbounded number of states. A finite automaton with access to two stacks is a more powerful device, equivalent in power to a Turing machine. A linear bounded automaton is a device which is more powerful than a pushdown automaton but less so than a Turing machine. PDA and Turing machines A pushdown automaton is computationally equivalent to a 'restricted' Turing Machine (TM) with two tapes which is restricted in the following manner- On the first tape, the TM can only read the input and move from left to right (it cannot make changes). On the second tape, it can only 'push' and 'pop' data. Or equivalently, it can read, write and move left