Pushdown Automata (PDA)

  A Pushdown Automata (PDA) can be defined as :  Q is the set of states ∑is the set of input symbols Γ is the set of pushdown symbols (which can be pushed and popped from stack) q0 is the initial state Z is the initial pushdown symbol (which is initially present in stack) F is the set of final states δ is a transition function which maps Q x {Σ ∪ ∈} x Γ into Q x Γ*. In a given state, PDA will read input symbol and stack symbol (top of the stack) and move to a new state and change the symbol of stack. Instantaneous Description (ID)  Instantaneous Description (ID) is an informal notation of how a PDA “computes” a input string and make a decision that string is accepted or rejected.  A ID is a triple (q, w, α), where:  1. q is the current state.  2. w is the remaining input.  3.α is the stack contents, top at the left.      Turnstile notation  ⊢ sign is called a “turnstile notation” and represents  one move.  ⊢* sign represents a sequence of moves.  Eg- (p, b, T) ⊢ (q, w, α)  This implies