PDA

• PUSHDOWN AUTOMATA (PDA)

  Pushdown Automata (PDA) are to context-free languages what deterministic, nondeterministic, and ε-transition automata are to regular languages.

  Key ideas:

  • A PDA is an automaton with ε-transitions with a stack of symbols.
  • This allows for the possibility to memorize an unlimited amount of information.
  • Access to the stack is only at its top (LIFO- Last In, First Out).
  • Similar behavior to automata with ε-transitions, where in each transition it is possible to consult and/or replace the top of the stack.
• PUSHDOWN AUTOMATON

  
• PDA, FORMALLY

  A) states

  B) input symbols

  C) stack alphabet

  D) initial state

  E) starts

  F) final states

  
• PDA, FORMALLY (cont.)

  The result of the function is a set of pairs (p,γ) where p ∈ Q and γ represents a set of symbols to replace the top of the stack:

  • if γ = ε then the top of the stack is discarded
  • if γ = X then the stack undergoes no changes
  • if γ = YZ then X is replaced by Z and Y is placed on top of the stack

  
• GRAPHICAL NOTATION

  
• EXAMPLE

  
• PDA OF EXAMPLE

  
• EMPTY STACK VS FINAL STATE

  A PDA defines two languages:

  • N(P) Accept by empty stack
  • L(P) Accept by reaching a final state

  Expression power of both languages is equal
• INSTANTANEOUS DESCRIPTION

  Intuitively, the PDA goes from configuration to configuration in response to input symbols (or sometimes ε), but unlike previous automata where the only thing we need to know about the automaton was the current state, in the PDA, the configuration involves both the state and the stack.

  Being infinite, the stack is usually the most important part of the PDA’s total configuration.
• INSTANTANEOUS DESCRIPTION (cont.)

  Thus, the configuration of a PDA can be represented by (q,w,γ) where

  • q is the state
  • w is the remaining input
  • γ is the stack content

  By convention, the top of the stack is on the left in γ. This triplet is called an instantaneous description (ID).
• INSTANTANEOUS DESCRIPTION (3/3)

  This movement reflects the idea that by consuming an a (which can be ε) from the input and replacing X on top of the stack with α, we can move from state q to state p.

  Note that what remains in the input w and what is below the top of the stack β, does not influence the action of the PDA.

  We use ∗⊢ to represent zero or more steps (computation).

  
• EXAMPLE

  
• LANGUAGE OF A PDA - ACCEPTANCE BY FINAL STATE

  
• LANGUAGE OF A PDA - ACCEPTANCE BY EMPTY STATE

  
• EQUIVALENCE BETWEEN EMPTY STACK AND FINAL STATE

  
• EQUIVALENCE BETWEEN EMPTY STACK AND FINAL STATE

  
• EQUIVALENCE BETWEEN EMPTY STACK AND FINAL STATE (cont.)

  
• EQUIVALENCE BETWEEN EMPTY STACK AND FINAL STATE