Difference Between Pushdown Automata And Finite Automata

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