What is theory of automata?

This subject is a fundamental subject and it is study to know about the compilers design, operating system, and system software. The automata theory is the base of this subject.

Theory of automata is the branch of computation theory in which we study about the abstract computing mechanisms and machines .It has been extended in many directions like modeling computation, real time and embedded systems or complexity theory. An automaton is defined as a system in which energy; information is transformed for performing some functions without the direct involvement of man. An automaton is a machine that performs computation on an input by moving through transitions from one state to another. If it is reach at accepting state then it will accept the input. These computations are used to represent various mathematic al models. There are many types of model such as finite automata, pushdown automata and Turing machine.

Why we study automata theory?

1)      Turing tell us the boundary between what an abstract machines could do and what it could not do.

2)      Stephen  Cook defines “intractable “ and NP-hard problems which can be solved easily but in practice they take so much time that computers are useless.

Finite automata:

A Finite automaton is a machine which moves on an input through transitions by moving one state to another. There are 5 tulles of finite automata represented by (Q, ∑, q0, F, δ) where

Q is the finite non empty set of states.

∑   is finite non empty set of inputs called input alphabet.

 q₀ ϵ Q is the initial state.

  F is the set of final states.

 Δ is a transition function which describes the change of states during the transition. It is also called the next state function.

Block diagram of finite automata





Description of block diagram:

1)      Input tape:  A Finite automata has an input tape. This input tape is divided into squares and each square contain a string symbol. At the rightmost and leftmost there are two symbols called end markers.

2)      Reading head: The arrow at the above of finite control is called reading head. As it reads an input symbol it moves one square either at left to right or right to left.

3)       Finite control: It controls the movement of reading head and also over the reading head to the next state.

Finite State Machine (FSM): It is a device which starts working from initial state and after reaching at final state it stops working and it accepts the string. The string is the sequence of the input symbols. In FSM there are 5 tulles which we studied above will be described by directed graphs?

In graph there are vertices in shape of circles called states. The path between two states is called transition. When there is double circle on a state then it will define the final state. When there is an arrow symbol at the starting of any state it means it is a final state. The alphabets are written on paths are called input symbols which together make a string.

In above figure 1,2,3,4 are the states.1 is the initial state.4 is final state and a, b, c alphabets are input symbols. There may be more than one final states and also more than one transition states.The transitions are describes as follows:

1)      1 state reads a symbol “a” and goes to the state 2.

2)      Similarly state 2 reads symbol “b” and go to state 3.

3)       State 3 reads “c” and go to state 4.

4)      State 4 reads “c” and go to state 4.