Finite State Machine by M. Arokiasamy

Power point presentation on Finite state machine by M. Arokiasamy.

1. Introduction
to

2. 1.Information-Processing Machine (IPM)
2.Examples.
3.Machines withmemory.
4.Machines withoutmemory.
5.What is a state?
6.Definition of Finite State machines(FSM).
7.Binary Devices and States.
8.Digital Computers-Are they FSM?
9.Properties of FSM.
10.Graphical representation of states.
11.Representation of FSM.

3. INFORMATION -PROCESSING MACHINE
ByanInformation-ProcessingMachine(IPM)we
meanadevicethatreceivesasetofinputsignalsand
producesacorrespondingsetofoutputsignalsas
illustratedinfigure.
IPM
Input Output
Signal Signals

4. Example
A (Table) lamp is an Information
Processing Machine
Input Signal : UP or DOWN position
of the switch
Output Signal: LIGHT or DARK.

5. In general, the input signals to an IPM change
with time.
In that case, the output signals will also
change with time accordingly.
i.e., in general an IPM receives a (time)
sequence of input signals and produces a
corresponding(time) sequence of output
signals.

6. In the example of Table lamp, the corresponding to the
sequence of input signals
UP DOWN DOWN UP DOWN UP UP…
There is a sequence of output signals
LIGHT DARK DARK LIGHT DARK LIGHT LIGHT…

7. Theoutputsignalatanyinstantdependsonlyon
theinputsignalatthetime,anddoesnotdepend
ontheinputsignalsbeforethatinstant.
Ontheotherhand,inthecaseofcalculator
(scientific)orcomputertheoutputsignalatany
instantdependsNOTonlyontheinputsignalat
thatinstantbutalsointheprecedinginput
signals.

8. MACHINES
1.Machines withmemory.
2. Machines withoutmemory

9. .
For a machine without memory its output at any
instant depends ONLY on the input at that instant.
The Table lamp is an example of machine without
memory.
Machines without memory

10. For a machine with memory, its output at any instant
depends on the input at that instant as well as on the input
at previous instants because the machine can remember
“what has happened in the past”
Clearly a Calculator and a Computer can remember what
had happened in the past.
Machines with memory

11. To describe past events, we introduce the notion of a
STATE.
A STATErepresents a summary of the past
history of the machine
Further more, as additional input signals arrive, the
machine will go from one state to another(NEXT
STATE) since it needs to update the summary of its
history.

12. A machine with a finite number of states is
called a finite state machine.

13. Wethinkofamachineasasystemthatcan
acceptinput,possiblyproducesoutput,and
havesomesortofinternalmemorythatkeep
trackofcertaininformationaboutprevious
inputs.
Thecompleteinternalconditionofthe
machineandallofitsmemory,atany
particulartime,issaidtoconstitutetheSTATE
ofthemachineatthattime.

14. Thedevicessuchasmechanicalswitches,diodes,
magneticdipoles,andtransistorsaretwostate(or
binary)devices.
Thetwostatesmayberealizedascurrentorno
current,magnetizedornotmagnetized,high
potentialorlowpotential,closedoropen,andonor
off.
Normallycurrentissimplydenotedby1anno
currentisdenotedby0.
Fromamathematicalstandpoint,wemaythinkthat
anytwostatedeviceconsistsofonlytwostates
namely0or1.

15. Sofarwehavelearnedtheconceptswhichispurely
mathematicalinnature.
EgSets,Relations,Functions,productofsets,
Graphsetc..
Nowweencounterthenotionthatwouldbeusedto
characterizemathematicallythefunctioningofthe
digitalcomputers.

16. Althoughtherearemanykindsofdigital
computers,theyareallFinite-state
machines(Finiteautomata)inthesenseof
havingthefollowingproperties
PropertiesofFiniteMachines-ASSIGNMENT!
[Reference:ModernAppliedAlgebrabyGarrettBirkhoff&
ThomasC.Bartee(pg.64-65)]

17. Almostalldigitalcomputers(digitalmachinesofanysort)
arecomposedofCircuitsandotherdeviceswhichare
bistableintheiroperation.
Justastheelectronicalsignalsusedindigitalcomputers,
thecircuitsarealsodesignedsothattheyarestablein
onlytwostables.
Thestateofanymachine(automation)consistingofa
finitenumberofbistabledevices.

18. Definition:
A Finite State machineor Finite State Automatonis specified
by the following six things:
(i)A finite set of states S={s
0, s
1, s
2,..}.
(ii)A special element of the set S, s
ois referred to as the initial
state.
(iii) A finite set of input letters I={i
1, i
2, i
3 ,…} .
(iv) A finite set of output letters O={o
1, o
2, o
3,…}.
(v) A function ƒ : SxI S , referred to as the TRANSITION
function.
(vi) A function g : SxI O , referred to as the OUTPUTfunction.

19. Atanyinstant,aFSMisinoneofits
states.
Uponthearrivalofaninputletter,the
machinewillgotoanotherstate
accordingtothetransitionfunction.
Furthermore,ateachstatethemachine
producesanoutputletteraccordingto
theoutputfunction.
Attheverybeginning,themachineisin
itsinitialstateS
0.

20. AFSMisthereforedefined
mathematicallybythreesetsS,I,and
Oandtwofunctionsfandg.
Itactsby‘reading’or‘accepting’a
sequenceorstringofinputsymbols
(theprogram)andthen‘printing’or
‘delivering’,outputsymbols.

21. i
k
S
0
o
k
s
j
A FSM starts in some internal state S
0(initial state)
then it reads the first input symbol i
k.
ThecombinationofS
0andi
kcausesanoutput
symbolo
ktobeproducedthroughtheoutput
functiongandthemachinegoestothenewstateS
j
asdirectedbythetransitionfunctionf.
Afterthis,themachinereadsthenextinputsymbol,
andsoonuntilitfinishesthestring.

22. i
k
S
0
o
k
s
j
The above diagram can be redrawn as:
S
0 s
j
I
k , o
k
OR
Initial
State
Next
State
Input, output

23. Representation of FSM
There are two ways of representing a FSM
1. State Table.
2. State Diagram