Understanding the Basics
In the realm of formal languages, we start with regular languages, which are recognized by regular finite automata. As we move to more complex languages, specifically context free languages (CFL), we need a more powerful machine called the Pushdown Automata (PDA).
A PDA is essentially a finite automaton equipped with a stack memory. This stack allows the machine to keep track of an arbitrary amount of information, making it capable of recognizing context free languages.
Components of Pushdown Automata
A typical pushdown automaton can be thought of as comprising two main parts:
Tape with Inputs: This is where the input string is read.
Stack Memory: This is used for storing symbols that can be pushed (added) or popped (removed) during the computation.
Types of Pushdown Automata
There are two types of PDAs:
Deterministic Pushdown Automata (DPA): Where each state has at most one possible action for each input.
Nondeterministic Pushdown Automata (NPA): Where each state can have multiple possible actions for an input. NPAs are more powerful and can accept all context-free languages.
Example Transitions
Consider an example transition:
Q12 (yes or no)-> (aaaabbbb, then aaaaaaaa on stack): For every ‘b’ seen in the input, an ‘a’ is popped from the stack. This corresponds to recognizing strings of the form A^nB^n.
Another transition example is:
Q36-(a,b->c)>Q216: This is akin to a finite automaton graph. Here, ‘a’ is seen in the input, ‘b’ is on the stack, and ‘c’ is pushed onto the stack.
Nondeterministic Example
In a nondeterministic scenario, one state Qx can have multiple possible outcomes. For instance:
Q36-(a,b->c)>(Q12,Q23): Here, reading ‘a’ in the input and ‘b’ on the stack can lead to either Q12 or Q23.
Special Transition
A special kind of transition is:
Qx-(a, epsilon->epsilon): This means do nothing when ‘a’ is read and the stack has epsilon (empty symbol). The dollar sign ($) often represents the bottom of the stack.
Example Automata
Example 1: A^nB^n
Qx-(epsilon, epsilon->$)>Q2(a,epsilon->x)-(b,x->epsilon)>Q3(b,x->epsilon)-(epsilon,$->epsilon)>Qf
Here, the PDA recognizes strings where the number of ‘a’s equals the number of ‘b’s.
Example 2: A^mB^n where m=!n
Q1-(epsilon, epsilon->$)>Q2(a,epsilon->a)-(b,a->epsilon)>Q3(b,a->epsilon)
State Q3 can handle two scenarios:
More ‘b’s than ‘a’s: Q3-(b,$->epsilon)>Qf(b,epsilon->epsilon)
More ‘a’s than ‘b’s: Q3-(epsilon, a->epsilon)>Qf(epsilon, $->epsilon)>Qf
Formal Definition
A nondeterministic pushdown automaton is defined by a 6-tuple:
(Q, Sigma, Gama, Delta, Q0, F)
Q: Finite set of states
Sigma: Finite input alphabet
Gama: Finite stack alphabet
Delta: Transition function
Q0: Starting state
F: Accepting states
The transition function Delta is defined as:
Delta: Q * Sigma * Gama -> P(Q * Gama)
For instance, Delta(q1, a, b) = {(q2, c), (q3, d)} means that in state q1, reading ‘a’ from the input and ‘b’ from the stack can transition to either q2 pushing ‘c’ or q3 pushing ‘d’.
