Formal Definition of Automata | FSM | 5-Tuple Machine


Ø  An automaton is Quintuple or 5-tuple machine.
Ø  It is represented by

M= (Q, ∑, δ, q0, 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
·     q0 is the initial state from where any input is processed (q0  Q).
·     F is a set of final state/states of Q (F Q).
Ø  Example of lift control:

SFL____________________2___q2
FFL____________________1___q1
GFL____________________0___q0

            Q={ q0 , q1 , q2},         ∑={0,1,2},
q0=Initial State,           F={ q2 } 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
δ( q0, 0)= q0          ,δ (q0,1)= q1    ,δ ( q0,2 )= q2
δ( q1, 0)= q0          ,δ (q1,1)= q1    ,δ ( q1,2 )= q2
δ( q2, 0)= q0          ,δ (q2,1)= q1    ,δ ( q2,2 )= q2

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.

Comments

  1. Blackjack, Slot Machines, and Slots | DRMCD
    Best 부천 출장마사지 Blackjack, Slot Machines, and Slots for Real Money | Slot Machine 화성 출장샵 Games 수원 출장샵 | Play Blackjack for Free at 경기도 출장샵 DRMCD. 전주 출장샵

    ReplyDelete

Post a Comment

Search related post on google