Finite Automata Explained | Board Infinity

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