Introduction to Finite Automata

Finite automate or finite state machine can be thought of an a severely restricted model of a computer.

Every computer has a central processing unit; it executes a program stored in a memory. This program normally accepts some input and delivers processed results.

The word Automata is for automation. A system where emery and information are transformed and used for performing some functions without direct involvement of men is called automaton.

A finite automata is also called a finite state machine.

A finite state machine is a mathematical model for actual physical process. By considering the possible inputs on which these machines can work, we can analyse their strengths and weaknesses.

Finite automata is used for solving several cmmon types of computer algorithm algorithms. Some of them are:

  1. 1. Design of digital circuits.
  2. 2. String matching.
  3. 3. Communication protocols for information exchange.
  4. 4. Lexical analyse of a typical compiler.

Working of Finite Automata

Let us consider a T-flip flop.

A T-flip-flop has:

  1. 1. One input denoted by T.
  2. 2. Two outputs denoted by Q and Q dash.
  3. 3. It has two distinct states, defined by the logical values of Q. The flip-flop is in q0 state when Q = 0 and it is in q1 state when Q = 1.
  4. 4. A value of 1 applied to its input changes its state from q0 to q1 or from q1 to q0.
Finite Automata - T flip-flop
T Flip – Flop

How T flip flop work?

T flip-flop is create using JK flip flop in which we are giving the same input to J and K. In T flip-flop working as if input in 1 then the output will get shift 1 to 0 or 0 to 1. And if the input is 0 then the output will remain the same.

Use of T flip-flop is to check if number of 1’s in string or sequence are Even or Odd.

A T flip-flop can be used to check whether an input binary number contains an even number of 1’s. Let us assume that a binary number 101110011 is applied to input T of the flip-flop. The initial state of the flip-flop is q0 (Q=0).

Input (T)101110011
State (Q)q1q1q0q1q0q0q0q1q0
State transition of T flip-flop under the input 101110011

From the above table , it should be clear that every even number of 1’s in input will make the T flip-flop toggle twice and it will be back to q0. Thus we can conclude the following:

  1. 1. If the initial state of flip flop is q0, it will come back to q0 if the input number contain even number of 1’s.
  2. 2. A single T flip-flop can be used as a machine for checking whether a binary number contains an even number of 1’s.

The machine starts with initial state q0 and after feeding the binary number, if the machine is found to be in q0, the input binary number contains an even number of 1’s.

Working of finite automate can be understood with the help of an abstract model of a finite automata. It is shown fig.

Finite Automata -  Model of a finite state machine

Operation of the finite automata is given below:

Input string is fed to the machine through a tape. Tape is divided into squares and each square contains an input symbol.

The main machine is shown as a box. Machine could be in any of the internal states (q0, q1, q2, q3, q4, q5).

Initially, the machine is in the starting (initial) state q0. Reading head is placed at the leftmost square of the tape.

At regular intervals, the machine reads one symbol from the tape and then enters a new state. Transition to a state depends only on the current state and the input symbol just read.
δ (qi, Aj) ⇒ qj
Machine transits from qi and qj on input Aj.

After reading an input symbol, the reading head moves right to the next square.

This process is repeated again and again.

  • A symbol is read.
  • State of the machine (finite control) changes.
  • Reading head moves to the right.

Everntually, the reading hes to say ‘Yes’ or ‘No’. If the machine ends up in one of a set of finite states (q2, q3) then the answer is ‘Yes’ otherwise the answer is ‘No’.

Recommended:

  1. Automata Theory and Formal Languages
  2. Kleene Closure
  3. Recursive Definition of a Language
  4. Finite Representation of language

Leave a Comment

Your email address will not be published. Required fields are marked *

x