PDA and Context-free Languages
Every context-free grammar can be transformed into an equivalent 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 is constructed as follows.
- for each rule (expand)
- for each terminal symbol (match)
As a result we obtain a single state pushdown automaton, the state here is, accepting the context-free language by empty stack. Its initial stack symbol equals the axiom of the context-free grammar.
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 .
Read more about this topic: Pushdown Automaton
Famous quotes containing the word languages:
“Science and technology multiply around us. To an increasing extent they dictate the languages in which we speak and think. Either we use those languages, or we remain mute.”
—J.G. (James Graham)