UNSOLVED cs 402 gdb solution fall 2020

[Muhammad Furqan Jalib 0]

CS 402 GDB 1 SOLUTION FALL 2020 1.docx CS 402 GDB 1 SOLUTION FALL 2020 2.docx

[zaasmi]

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:

1. 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.

2. 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.

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

4. 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.