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.