## What Is Pushdown Automata?

A pushdown Automata is essentially
a finite automaton with an auxiliary data structure (extra memory) known as a **stack**, which helps Pushdown automata to
recognize Context Free Languages. Pushdown automata are used in theories about
what can be computed by machines. They are more capable than finite-state
machines but less capable than Turing machines.

A pushdown automaton has three components:

**An input tape****A control unit****A stack with infinite size**

**A stack** consists of a finite list of symbols. Symbols can be added
to and removed from the list, but only at one end of the list. The end of the
list where items can be added and removed is called the top of the stack. The
list is usually visualized as a vertical ‘’stack’’ of symbols, with items being
added and removed at the top.

Adding a symbol at the top of the
stack is referred to as **pushing** a
symbol onto the stack and removing a symbol is referred to as **popping** an item from the stack. During
each step of its computation, a pushdown automaton is capable of doing several
push and pop operations on its stack (this in addition to possibly reading a
symbol from the input string that is being processed by the automaton).

Pushdown automata can be categorized into types:

**Deterministic Pushdown Automata****Nondeterministic Pushdown Automata**

Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic pushdown automata can recognize all context-free languages, with the former often used in parser design.

### What You Need To Know About Pushdown Automata

- A pushdown automaton (PDA) is a type of automata that employs a stack.
- It has the additional stack for storing long sequence of alphabets.
- Pushdown Automata can be constructed for Type-2 grammar.
- Input alphabets are accepted by reaching: Empty stack and Final state.
- Non-Deterministic Pushdown Automata (NDPA) has more capability than Deterministic Pushdown Automata (DPDA).
- Pushdown automata can be constructed for context free grammar.
- Not every Non-Deterministic pushdown automata is transformed into its equivalent Deterministic Pushdown Automata.

## What Is Finite Automata?

A finite Automaton (FA) is a simple idealized machine used to recognize patterns within input taken from some character set (or alphabet). The main function of a finite automaton is to accept or reject an input depending on whether the pattern defined by the FA occurs in the input. It has a set of states and rules for moving from one state to another but it depends upon the applied input symbol. Basically it is an abstract model of digital computer.

A Finite Automata consists of the following:

- Finite set of states
- Set of Input Symbols
- Initial State
- Set of Final States
- Transition Function

Finite Automata is characterized into two types:

- Deterministic Finite Automata (DFA)
- Non-Deterministic Finite Automata (NFA)

### What You Need To Know About Pushdown Automata

- A Finite Automaton (FA) is a simple idealized machine used to recognize patterns within input taken from some character set.
- It doesn’t have the capability or space to store long sequence of input alphabets.
- Finite Automata can be constructed for Type-3 grammar.
- Input alphabets are accepted by reaching ‘’final states’’.
- Non-Deterministic Finite Automata (NFA) has same capability as Deterministic Finite Automata (DFA).
- Finite automata can be constructed for regular language.
- Every Non-Deterministic Finite Automata is transformed into an equivalent Deterministic Finite Automata.

## Difference Between Pushdown Automata And Finite Automata

BASIS OF
COMPARISON |
PUSHDOWN
AUTOMATA |
FINITE
AUTOMATA |

Description | A pushdown automaton (PDA) is a type of automata that employs a stack. | A Finite Automaton (FA) is a simple idealized machine used to recognize patterns within input taken from some character set. |

Space | It has the additional stack for storing long sequence of alphabets. | It doesn’t have the capability or space to store long sequence of input alphabets. |

Construction
| Pushdown Automata can be constructed for Type-2 grammar. | Finite Automata can be constructed for Type-3 grammar. |

Input
Alphabets | Input alphabets are accepted by reaching: Empty stack and Final state. | Input alphabets are accepted by reaching ‘’final states’’. |

Capability | Non-Deterministic Pushdown Automata (NDPA) has more capability than Deterministic Pushdown Automata (DPDA). | Non-Deterministic Finite Automata (NFA) has same capability as Deterministic Finite Automata (DFA). |

Flexibility | Pushdown automata can be constructed for context free grammar. | Finite automata can be constructed for regular language. |

Transformation
| Not every Non-Deterministic pushdown automata is transformed into its equivalent Deterministic Pushdown Automata. | Every Non-Deterministic Finite Automata is transformed into an equivalent Deterministic Finite Automata. |