Pushdown Automaton - PDA and Context-free Languages

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.

  1. for each rule (expand)
  2. 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:

    People in places many of us never heard of, whose names we can’t pronounce or even spell, are speaking up for themselves. They speak in languages we once classified as “exotic” but whose mastery is now essential for our diplomats and businessmen. But what they say is very much the same the world over. They want a decent standard of living. They want human dignity and a voice in their own futures. They want their children to grow up strong and healthy and free.
    Hubert H. Humphrey (1911–1978)