CS 402 GDB 1 SOLUTION FALL 2020
FINITE AUTOMATA (FA):
Finite Automata
= PDA with finite stack.
= TM with finite tape.
= TM with unidirectional tape.
= TM with read only tape.

PUSH DOWN AUTOMATA (PDA):
PDA = Finite Automata with Stack

TURING MACHINE ™:
Turing Machine
= PDA with additional stack.
= FA with 2 stacks.
The Applications of these Automata are given as follows:

Finite Automata (FA) –
• For the designing of lexical analysis of a compiler.
• For recognizing the pattern using regular expressions.
• For the designing of the combination and sequential circuits using Mealy and Moore Machines.
• Used in text editors.
• For the implementation of spell checkers.

Push Down Automata (PDA) –
• For designing the parsing phase of a compiler (Syntax Analysis).
• For implementation of stack applications.
• For evaluating the arithmetic expressions.
• For solving the Tower of Hanoi Problem.

Linear Bounded Automata (LBA) –
• For implementation of genetic programming.
• For constructing syntactic parse trees for semantic analysis of the compiler.

Turing Machine ™ –
• For solving any recursively enumerable problem.
• For understanding complexity theory.
• For implementation of neural networks.
• For implementation of Robotics Applications.
• For implementation of artificial intelligence.