Automata Tutorial

What is Automata?

Automata is a mathematical model and abstract model, which is used to detect string in various languages. In Automata,

Regular language is recognized by Finite state Automata
Context Free language is recognized by Push down Automata
Context sensitive language is recognized by linear bounded Automata
Recursive Enumerable Language is recognized by Turing Machine.

What do you mean by Finite Automata?

Finite state Automata or Finite State Machine are the simplest model used in Automata. Finite state automata accept regular language. The term finite means it has a limited number of possible states, and number of alphabets in the strings are finite.

Finite state Automata is represented by 5 tuples or elements (Q, ?, q₀, F, ?):

Q: It is a collection of finite set of states.

?: It is a finite set of input Symbols called the alphabet of the automata.

q₀: It is used for representing initial state of the finite automata from where the starting of the input is processed.

F: It is a collection of finite set of final states.

?: It is used for representing Transition Function. The states of Finite Automata move from one state to another state in response to some inputs by using transition function. The transition function is given by Finite State automata are:

Q x ? -> Q

Examples:

The example of Finite state Automata is Automatic door controller because it has limited memory for detecting the present state of the controller, automatic doors are often found at entrance and exists of various hotels, supermarkets, theaters and hospitals etc. Automatic door have two pads that are used for detection:

Front Pad: This is located at front of the doorway to detect the presence of the person.

Rear Pad: This pad is located at backside of the doorway. In this, controller hold the door to open till the person passes all the way through it.

Some other examples of finite automata are elevator, digital watches, dish washes and calculators.

Important features of Finite Automata

Input: Finite Automata takes some input and with the use of this input we can produce some output. The input of the automata is given in the input tape used in the automata. This tape is divided into cells or squares which can hold one symbol at a time.

Output: Finite Automata produce some output with the use of some input.

States of Automata: Automata have finite number of input states. States of Automata like q₀, q₁…q_n.

State Relation: State relations show how automata moves from one state to another state. The next state of the automata at any instant of time is determined by the present state and the input.

Advantages of finite Automata

Below are some advantages of Finite State Automata and Finite State Machine:

Finite state machines are very flexible.
Well suited for domains where execution time is shared between various modules.
In finite state automata, we can easily determine the reachability of an input state whether it is accepted or rejected.

Disadvantages of finite Automata

Below are some disadvantages of Finite State Automata and Finite State Machine:

Finite state Automata have very limited amount of memory.
Various multiplications operations on large numbers cannot be carried out on finite automata, because it has limited memory and it cannot remember the full-length sequence of large numbers.
Not applicable for all types of applications.
Finite state Automata cannot process Natural Language processes.
Finite state automata have less computational power than some other models of computation used in automata such as Push down Automata, linear bounded automata and Turing machine.

Applications of Finite Automata

Finite Automata is used in various fields like science, mathematics, and engineering. Below are some applications of finite automata:

Finite state Automata used in Word Processor Programs to provide features, which allow us to search for a given string.

It is used in Digital Logic Design to control units for a disk or an Input/output controller on a process.
It is used in Lexical Analysis phase in complier design.
It is used in various spell checker applications.
It is used in various Circuit switching design.
It is used in various text editors.