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