Unité d’Enseignement :

Concours Programmation

Gilles Menez

Université de Nice – Sophia-AntipolisDépartement d’Informatique

email : menez@unice.frwww : www.i3s.unice.fr/˜menez

12 novembre 2018: V 1.1

c©Gilles Menez 1

Finite State Machines

1. Introduction 31.1.State Machines 31.2.Such a useful framework ! 41.3.Finite Automata 5

2. Machines 72.1.FSM with Outputs 72.2.Mealy Machine 82.3.UnCiphering/Decoding machine 102.4.Prefix code 11

3. Moore Machine 15

4. Moore vs Mealy 17

5. Implementation techniques 205.1.Goto implementation 215.2."State Variable" implementation 235.3.Transition matrix implementation 28

6. Challenges 296.1.Rebound filtering 306.2.Vehicule identifiers classification 32

c©Gilles Menez 2

IntroductionState Machines

State Machines

Most of the time, State Machines are introduced when students learntheoretical fundations of software.

As a model of computations (i.e which describes how a set of outputs arecomputed given a set of inputs) their graphical representations (of course wedo not forget the underneath mathematical model) is often used to illustratefor example :

â the evolution of the Turing machine,â or if an input is accepted or rejected by the grammar of a formal language.â . . .

This close connexion to the theoretical could explain why, as these coursesfinish, the "state machine" model will be ASAP buried.

c©Gilles Menez 3

IntroductionSuch a useful framework !

Such a useful framework !State machines are such a general formalism that a HUGE class ofdiscrete-time system can be described as states machines.

ã They are useful frameworks for modeling/implementing systems.

Every day life systems will use them :ã Embedded systems (washing, espresso, *.* . . . machines),ã GUI software,ã Processes guidances (included protocols or OS),ã Complex systems operations (lifts, spacecrafts, . . . ),ã . . .

I do love the citation of Knuth (LATEXfather) (about operating algorithm ofcampus lift) in the conclusion (page 165) of :https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/

6-01sc-introduction-to-electrical-engineering-and-computer-science-i-spring-2011/unit-1-software-engineering/

state-machines/MIT6_01SCS11_chap04.pdf

c©Gilles Menez 4

IntroductionFinite Automata

Finite Automata

Finite Automata (FA) is the simplest machine to recognize patterns.

State Diagram of the FSA :"Floats in C language"

A FA consists of the following :â Q : finite set of states.â Σ : set of input symbols.â q : initial state (q is a mem-

ber of Q) .â F : set of final states (F is a

subset of Q).â δ : transition function.

δ : QxΣ −→ Q

Formal specification of this machineM is Q,Σ, q,F , δ

c©Gilles Menez 5

IntroductionFinite Automata

Input word : An automata reads a finite string of symbols a1, a2, . . . , an ,where ai ∈ Σ, which is called an input word.

4 The set of all words is denoted by Σ∗.

"Accept or Reject" : This is "the aim" of a Finite State Automata describedmachine.

Accepting word : A word w ∈ Σ∗ is accepted by the automaton if qn ∈ F(equiv. The final state deduced from transitions conducted by inputs/symbolsof the word w is in F )

We stop there because probably theses slides should be a remake and youshould know from L1/L2/L3 :

À Deterministic Finite Automata,Á Non Deterministic Finite Automata,

Several possible transitions from a state for a same input. Language recognized byM, . . .

c©Gilles Menez 6

MachinesFSM with Outputs

FSM with OutputsIn a theoretical context, FSA are "just" accepting or rejecting.

But some machines, described by FSA, have outputs :

â They are FSM : Moore Machines or Mealy Machines

They are intensively used to control (all kind) of processes, . . . washingmachines, espresso machines, . . .

c©Gilles Menez 7

MachinesMealy Machine

Mealy MachineA Mealy machine is a deterministic finite-state transducer :

ã "deterministic" : for each state and input, at most one transition ispossible.

ã "transducer" : inputs will imply outputs.

Example : The following Mealy machine "determines whether the number of 1sis even or odd, for a given binary number."

As you see, in mealy machines outputs are on transitions !

c©Gilles Menez 8

MachinesMealy Machine

A Mealy Machine consists of the following :á Q : finite set of states.á Σ : set of input symbols (e.g. input alphabet).á q : initial state (q is a member of Q) .á δ : transition Function.

δ : QxΣ −→ Q

á Γ : set of output symbols (e.g output alphabet)á ω : output function

ω : QxΣ −→ Γ

Very similar to a Finite Automaton (FA), with a few key differences :â It has no final states.â Its transitions produce output :

It does not accept or reject input, instead, it generates output frominput.

â Lastly, Mealy machines cannot have nondeterministic states.c©Gilles Menez 9

MachinesUnCiphering/Decoding machine

UnCiphering/Decoding machineMealy machines provide a rudimentary mathematical model for "toy" ciphermachines :Considering the "input Latin alphabet" and "output {0, 1} alphabet", a Mealymachine can be designed that given a string of letters (a sequence of inputs) itcan process it into a ciphered bit string (a sequence of outputs) :

010101101000101101010110

Propose this input sequence to this "unciphering" machine and tell the input !

â Which string (in the Latin alphabet) is this ?

6 Inputs are in red color.6 Outputs are in blue color (ε is empty/no output).

c©Gilles Menez 10

MachinesPrefix code

Prefix codeCan you deduce the ciphering code (/prefix code) ?"Prefix code" : a set C of nonempty words is a prefix code if no word of C is aproper prefix of another word in C (i.e there is no whole code word in C that isa prefix (initial segment) of any other code word in C.).

ã For example, a code with code words 9, 55 has the prefix property ; a codeconsisting of 9, 5, 59, 55 does not, because "5" is a prefix of "59" andalso of "55"

ã aka, Huffman, Shannon-Fano, . . .

c©Gilles Menez 11

MachinesPrefix code

Construction of a FSM decoder for a code γ

The decoder for the encoding γ is built as follows :

4 Take a state for each proper prefix of some codeword : 1[1], 10[0],101[0,1] for state "2","3","4".

4 The state corresponding to the empty word ε is the initial and theterminal state : state "1".

4 There is an edge p a|ε−−→ pa for each prefix p and letter a, such that pa is(again/still) a prefix

4 There is an edge p a|b−−→ ε for each p and letter a with pa = γ(b).

Properties :ã When the code is prefix, the decoder is deterministic.ã In the general case, unique decipherability is reflected by the fact that the

transducer is unambiguous.

c©Gilles Menez 12

MachinesPrefix code

Deterministic / Unambiguous

An automaton is deterministic

ã if it has a unique initial state andã if, for each state p and each letter a, there is at most one edge starting in

p and labeled with a.

This implies that, for each state p and each word w, there exists at most onepath starting in p and labeled with w.

An automaton is unambiguous

ã if, for all states p, q and all words w, there is at most one path from p toq labeled with w.

Clearly, a deterministic automaton is unambiguous.

c©Gilles Menez 13

MachinesPrefix code

Automatic Teller Machine (ATM) instance

from : Ulyantsev, Vladimir & Buzhinsky, Igor & Shalyto, Anatoly. (2016). Exact Finite-StateMachine Identification from Scenarios and Temporal Properties. International Journal on Software

Tools for Technology Transfer. 10.1007/s10009-016-0442-1.c©Gilles Menez 14

Moore Machine

Moore MachineMoore machines aredifferent than Mealy ones in the output function, ω.

á In a Mealy machine output values are determined both by its current stateand the current inputs.

So output is produced by its transitions.á In a Moore machine, output (in red on figure) is produced by its states.

c©Gilles Menez 15

Moore Machine

Moore example : Gate operator

c©Gilles Menez 16

Moore vs Mealy

Moore vs Mealy

Moore Machine

4 Output is placed on states.4 So, output depends only upon present

state.4 If input changes, output does not

change (before clock triggering).4 More number of states are required.4 So there is more hardware requirement.4 They react slower to inputs (One clock

cycle later)4 Synchronous output and state genera-

tion.4 Easy to design.

Mealy Machine

4 Output is placed on transitions.4 Output depends on present state as well

as present input.4 If input changes, output also changes.4 Less number of states are required.4 There is less hardware requirement.4 They react faster to inputs.4 Asynchronous output generation.4 It is difficult to design.

c©Gilles Menez 17

Moore vs Mealy

Mealy Machine in/from Moore Machine

Moore <— transformation/conversion is possible –> Mealy

https://fr.wikipedia.org/wiki/Machine_de_Mealy

c©Gilles Menez 18

Moore vs Mealy

Synthetize a FSM

The "big problem" is often to "move" your implementation in the statemachine framework.

You have to synthetize the FSM from a specification :

â Traffic lights,â Sequence detector,â Lift control,â . . .

c©Gilles Menez 19

Implementation techniques

Implementation techniques

At least three solutions :À GotoÁ State variable Transition matrix

The good one ? . . .

It depends . . .â Size of code,â Size of data,â Changeability, scalabilityâ Coding context (challenge)

c©Gilles Menez 20

Implementation techniquesGoto implementation

Goto implementation

1

2 int main ( void ){3 char c ;4

5 goto E1 ; // Etat initial6

7 E1 :8 scanf ( "%c%*c" ,&c ) ; /∗ Ent r ee ∗/9 if ( c==’0’ ){10 printf ( "\t0␣\n" ) ; /∗ S o r t i e ∗/11 goto E1 ;12 }13 if ( c==’1’ )14 goto E2 ;15 goto END ;16

17 . . .

c©Gilles Menez 21

Implementation techniquesGoto implementation

Goto implementation

á It is unusual to promote goto and label ? In fact, NO !https://www.reddit.com/r/linuxmasterrace/comments/8fmn20/uses_of_goto_in_linux_kernel_source_over_versions/

á In the context of FSM, the "spaghetti" effect is under control since thespecification is given by the state diagram.

á "State" is in the code : No need for a variable, neither memory !

But as a consequence, it is "hard coded" !

á Fast to code and efficient to run for a specific automata.

Good for embedded applications !

c©Gilles Menez 22

Implementation techniques"State Variable" implementation

"State Variable" implementation1 # include <s t d i o . h>2 # define A 03 # define B 14 # define C 25 int main ( void ){6 int entree ;7 int etat = A ; /∗ Etat i n i t i a l ∗/8 for ( ; ; ) {9 switch ( etat ){10 case A : /∗∗ Etat : A ∗/11 /∗ Lec tu r e de l ’ e n t r e e ∗/12 scanf ( "%d" ,&entree ) ;13 /∗ Ca l c u l de l ’ e t a t s u i v a n t ∗/14 switch ( entree ){15 case 0 :16 etat = A ;17 printf ( "\t%d\n" , 0 ) ; /∗ S o r t i e ∗/18 break ;19 case 1 :20 etat = B ;21 break ;22 }23 break ;24 case B : /∗∗ Etat : B ∗/25 . . .

c©Gilles Menez 23

Implementation techniques"State Variable" implementation

"State Variable" implementation

á The value of the variable is the state.á Infinite for-loopá The structure of the FSM is in the code.á Low memory cost

c©Gilles Menez 24

Implementation techniques"State Variable" implementation

Transition matrix implementation I1 # include <s t d i o . h>2 // Author : http ://web.archive.org/web/20160808120758/http ://www.gedan.net/2009/03/18/finite-state-machine-matrix-style-c-

implementation-function-pointers-addon/34 typedef enum {5 STATE1 ,6 STATE2 ,7 STATE38 } state ;9

10 typedef enum {11 NILEVENT ,12 EVENT1 ,13 EVENT214 } event ;1516 typedef void (∗action ) ( ) ;17 typedef struct {18 state nextState ; // Enumerator for the next state19 action actionToDo ; // function-pointer to the action that shall be released in current state20 } stateElement ;2122 //Actions23 void action1_1 ( void ) ;24 void action1_2 ( void ) ;25 void action1_3 ( void ) ;26 void action2_1 ( void ) ;27 void action2_2 ( void ) ;28 void action2_3 ( void ) ;29 void action3_1 ( void ) ;30 void action3_2 ( void ) ;31 void action3_3 ( void ) ;3233 int main ( void ){

c©Gilles Menez 25

Implementation techniques"State Variable" implementation

Transition matrix implementation II34 stateElement stateMatrix [ 3 ] [ 3 ] = { // next state,action on transition35 { {STATE1 , action1_1 } , {STATE2 , action1_2 } , {STATE3 , action1_3} } ,36 { {STATE2 , action2_1 } , {STATE2 , action2_2 } , {STATE3 , action2_3} } ,37 { {STATE3 , action3_1 } , {STATE3 , action3_2 } , {STATE3 , action3_3} }38 } ;3940 //Initializations41 state currentState = STATE1 ;42 event eventOccured = NILEVENT ;43 action actionToDo = stateMatrix [ currentState ] [ eventOccured ] . actionToDo ;4445 while (1 ) {46 // event input, NIL-event for non-changing input-alphabet of FSM47 // in real implementation this should be triggered by event48 // registers e.g. evaluation of complex binary expressions could49 // be implemented to release the events5051 int e = 0 ;5253 printf ( "----------------\n" ) ;54 printf ( "Event␣to␣occure␣(uint)␣:␣" ) ;55 scanf ( "%u" ,&e ) ;5657 //determine the State-Matrix-Element in dependany of current state and triggered event58 stateElement stateEvaluation = stateMatrix [ currentState ] [ ( event ) e ] ;5960 // do the transition to the next state61 currentState = stateEvaluation . nextState ;6263 //... and fire the proper action64 (∗stateEvaluation . actionToDo ) ( ) ;6566 printf ( "-----------------\n" ) ;67

c©Gilles Menez 26

Implementation techniques"State Variable" implementation

Transition matrix implementation III68 } ;69 return ( 0 ) ;70 }7172 /∗∗∗ a c t i o n f u n c t i o n s ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗/7374 void action1_1 ( ) {75 printf ( "action1 .1␣\n" ) ;76 }77 void action1_2 ( ) {78 printf ( "action1 .2␣\n" ) ;79 }80 void action1_3 ( ) {81 printf ( "action1 .3␣\n" ) ;82 }83 void action2_1 ( ) {84 printf ( "action2 .1␣\n" ) ;85 }86 void action2_2 ( ) {87 printf ( "action2 .2␣\n" ) ;88 }89 void action2_3 ( ) {90 printf ( "action2 .3␣\n" ) ;91 }92 void action3_1 ( ) {93 printf ( "action3 .1␣\n" ) ;94 }95 void action3_2 ( ) {96 printf ( "action3 .2␣\n" ) ;97 }98 void action3_3 ( ) {99 printf ( "action3 .3␣\n" ) ;100 }

c©Gilles Menez 27

Implementation techniquesTransition matrix implementation

Transition matrix implementation

á The automata is in the data structure,á The code is independant of the automata topology.

c©Gilles Menez 28

Challenges

Challenges

2 challenges :

À Rebound filteringÁ Vehicule identifiers classification

c©Gilles Menez 29

ChallengesRebound filtering

Rewriting : Rebound filteringThe following example uses a Mealy machine to filter a bit sequence to removeisolated value occurence.

Input -> Output0 -> 0101 -> 11100101101 -> 0000111101100101001110 -> 0110000000111

Two remarks :

À The initial state (resuming the unknown past) is given by the first value ofthe sequence.

Á On the last caracter of the sequence, if you cannot conclued if it is a 0 ora 1, you remove it :

001 will give 00

c©Gilles Menez 30

ChallengesRebound filtering

Can you propose a FSM?

Remark : Why a FSM? You could try without ?â FSM is a formalism . . . to replace the natural language.â FSM approach will really get this exercise easier because implementation

will be straigth forward !

All the "understanding" of the solution is in the FSM !

c©Gilles Menez 31

ChallengesVehicule identifiers classification

Vehicule identifiers classificationFrom a speed limit control system, you get a string which has been proposedby an image recognition tool.

From this string, you would like to define and output if it is a car or amotorcycle (small or big) or a "bad recognition".If the picture is good, the recognition tool will produce :

À For a car/big motorcycle/. . . , a sequence of 2 upper case letters, 3 digitsand 2 upper case letters.

output will be : ’V’Á For a small motorcycle a sequence of 2 upper case letters, 2 digits and 1

upper case letters.

output will be : ’M’

If the picture was not sharp enought, you could get a "nonsense" sequencefrom the recognition which is different from standards.

output will be : ’ ?’c©Gilles Menez 32

Index

Index

Index :

c©Gilles Menez 33