Automata Theory AND Mathematical Model of Automata

What is Automata Theory?

A computer is  an automatic computing device which is programmable also. A user of computer can instruct the computer to do whatever he/she wants. Computer has four main components .Memory of computer is finite.

• Input (Input device just like keyboard,mouse, joystick etc.).
• Output(Output device just like printer ,monitor etc.).
• Memory(Memory just like RAM,Hard disk etc).
• Processor(That is control unit of computer.).

There are many earlier automatic machine first calculating device was abacus. That abacus is used to perform arithmetic operation like addition,multiplication  etc.Typically consist of rectangular frame with thin parallel rods(strung with beads).

Mathematicians had build an abstract model of computing device like computer. That mathematical models are

• Finite Automata(FA). That is also two types. Finite automata with output and finite automata without output.
• Pushdown Automata(PDA).
• Linear Bounded Automata(LBA).
• Turing machine(TM).

Mathematicians try to explain the abstract concept of  automatic machines using these four models. That model  also has input,memory ,control and output.That model use tape as input and output  device and also finite control that move left to right .That model use stack for storage purpose. 

The automaton described by state diagram. q0 is starting state and q1 is dead state and q2 is final state.

That automata accept  set of  string that is start with a is accepted  and other string are rejected.  

 Regular expression=a(a+b)*.

    

Automata theory is relate to formal language.There are four type of model and according to chomsky classification four type of language in automata.

• Regular Language(Finite automata).
• Context free language(Pushdown automata).
• Context sensitive language(Linear bounded automata).
• Recursive language(Turing machine).

Regular grammar is also called Type 3 .Context free grammar also called Type 2 .Context sensitive grammar also called Type 1. Recursive enumerable grammar is called Type 0.

The language recognized by FA are called regular language and these language are described by simple expression called regular expression.

• Class Type 0,Grammar unrestricted,language recursively enumerable,automaton Turing machine.
• Class Type 1,Grammar Context sensitive,language context sensitive, automaton linear bounded.
• Class Type 2,Grammar Context free,language context free, automaton push down.
• Class Type 3,Grammar Regular,language Regular, automaton finite.