Finite Automata Explained

Introduction

Finite automata are a type of abstract computer. It is a mathematical representation of a system having discrete inputs, outputs, states, and a series of state-to-state transitions that take as input alphabetic symbols.

Automata Finite Representation

Three representations for the finite automata are shown below.

  • Graphical (Transition diagram)
  • Tabular (Transition table)
  • Mathematical (Transition function)

Formal definition of Finite Automata :

Finite automata is defined as a 5-tuples

M=(Q, Σ, δ,q0,F)

  • Q: Finite set called states.
  • Σ: Finite set called alphabets.
  • δ: Q × Σ → Q is the transition function.
  • q0 ∈ Q is the start or initial state.
  • F: Final or accept state.

Illustration for Finite Automata

Finite Automata can be illustrated with the following:

  • Transition diagram
  • Transition table
  • Transition function

Transition diagram

It is a directed graph, with the states of finite automata represented by the graph'sTransitional Chart

It is a directed graph, with the states of finite automata represented by the graph's vertices.

Below is a transition diagram example in 0 and 1: Inputs

q1: Initial condition

Question two: Middle state

qf: End result

Transition table

The transition function, which requires two arguments (a state and a symbol) and returns a value (the "next state"), is essentially represented in a tabular format.

δ : Q × Σ → Q

The following variables are taken into account in the transition table:

  • States are represented by rows.
  • The input symbol is corresponding to the column.
  • Entries match the following state.
  • -> designates the start state.
  • the accept state indicated by a star.

Transition function

stands for the transition function. The passes to this transition function are the two parameters listed below.

Present situation

Input symbol

A state that can be referred to as the next state is returned by the transition function.

Next state = (current state, current input symbol)

For instance, (q0, a)=q1