Pushdown Automata and Context Free Languages

Pushdown Automata §

• An extension of Finite Automata but with a special component called a stack that serves as additional (infinite) memory. We can push or pop symbols off of the stack.

• Formally, a (nondeterministic) pushdown automata is a -tuple where and are all finite sets. We denote and

  • is the set of all states
  • is the input alphabet.
  • is the stack alphabet.
  • is the transition function.
  • is the start state.
  • is the set of accept states.

• It accepts where each and the sequences of states and strings representing the stack contents that has on the accepting branch of the computation.

  1. . Start on the start state with an empty stack.

  2. For we have that

     Where and for and . Move properly according to state, stack, and next input. That is, at state , with at the top of the stack and popping symbol , the next move is move to state and push symbol .

  3. . Accept state occurs at input end.

• We may test for an empty stack by testing for a special delimiter $$$.

• We may test if the machine reaches the end of the input string by assuming the accept state only takes effect when the machine is at the end of the input.

• Sipser 2.20: A Language is context free if and only if some PDA recognizes it. ¹

Context Free Grammar §

• A context free grammar is a -tuple where the production rules are of the form , .

• A CFG is in Chomsky Normal Form if every rule is of the form

• Sipser 2.9: Any Context Free Language is generated by a CFG in Chomsky Normal Form. That is, we can convert any CFG into Chomsky Normal Form

Non-Context Free Languages §

• Sipser 2.34: Pumping Lemma for CFLs If is a CFL, then there is a number called the pumping length where if is any string in of length at least , then may be divided into five pieces satisfying the following conditions: ²

2. and
3. .

Links §

• Sipser Ch. 2

Footnotes §

1. Sipser provides a proof. The idea is to establish an algorithm to convert from PDA to CFG and vice versa. This boils down to mapping states with nonterminals, and symbols (Including those pushed into the stack) with the terminals plus the nonterminals. ↩

2. Like the Regular Language version, the pumping lemma holds because of the Pigeonhole Principle. The Pigeonhole Principle applies because every set in the Grammar is finite so we can simply use a string that is long enough such that in the parse tree, we have to use a production rule twice. Conditions 2 and 3 are there to make sure we don’t have any pathologies when using the Pigeonhole Principle. ↩