Can PDA have two final states.

can pda has accept two states ?

Vaishali @vaishalij
7 Sep 2017 07:53 pm

Yes a pda can have two accepting/final states. If you look at the Formal definition of a PDA, 

A PDA is formally defined as a 7-tuple:

M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F) where

\,Q is a finite set of states

  • \,\Sigma  is a finite set which is called the input alphabet
  • \,\Gamma  is a finite set which is called the stack alphabet
  • \,\delta  is a finite subset of Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma \times Q\times \Gamma ^{*}, the transition relation.
  • \,q_{0}\in \,Q is the start state
  • \ Z\in \,\Gamma  is the initial stack symbol
  • F\subseteq Q is the set of accepting states

F is the set of accepting states, that means it can be any number of accepting states but should be a subset of Q.