Formal Definition of Automata

Ø  An automaton is Quintuple or 5-tuple machine.

Ø  It is represented by

M= (Q, ∑, δ, q₀, F), where −

·     Q is a finite set of states.

·     ∑ is a finite set of symbols, called the  input alphabet of the automaton.

·     δ is the transition function/mapping function which maps

Q x ∑ à Q   (Here x is Cartesian Product)

            Above mapping is usually represented by

1.   Transition function/Mapping function

2.   Transition diagram / Transition graph / Transition State diagram/ State diagram

3.   Transition table/Transition state table/Mapping table

·     q₀ is the initial state from where any input is processed (q₀ ∈ Q).

·     F is a set of final state/states of Q (F ⊆ Q).

Ø  Example of lift control:

SFL____________________2___q₂

FFL____________________1___q₁

GFL____________________0___q₀

            Q={ q₀ , q₁ , q₂},         ∑={0,1,2},

q₀=Initial State,           F={ q₂ } and δ is given by

1)Transition function:

By using the below formula we can easily write the transition functions

δ(Present State, Input Symbol)=Next State

δ( q₀, 0)= q₀          ,δ (q₀,1)= q₁    ,δ ( q₀,2 )= q₂

δ( q₁, 0)= q₀          ,δ (q₁,1)= q₁    ,δ ( q₁,2 )= q₂

δ( q₂, 0)= q₀          ,δ (q₂,1)= q₁    ,δ ( q₂,2 )= q₂

2)Transition diagram:

3)Transition Table:

Present State	Next State
	Input 0	Input 1	Input 2
àq0	q0	q1	q2
q1	q0	q1	q2
*q2	q0	q1	q2

Note: 
1)Final state/Accepting state in transition table can be represented by either  * or simple circle
2)An Automaton with finite number of states is called Finite State Machine or Finite Automata.