Finite State Machines Tutorial

From Progzoo

Revision as of 09:24, 2 March 2012 by Andr3w (Talk | contribs)

You can use a Finite State Machine to recognize some strings and reject others.

Contents

Finite State Machine for Decimals

This is a finite state machine that recognizes decimal numbers such as 123 and 0.123 and .789

It will not recognize strings such as 1.2.3 or 1a

Change the machine so that it allows the underscore character to be included in numbers. We should allow 1_234 and 1.123_4

A Finite State Machine


[Font] [Default] [Show] [Resize] [History] [Profile]

Finite State Machine for Decimals with Exponent

Complete the finite state machine so that recognizes decimal numbers with an exponent such as 123 and 0.123 and 4.7E10

It will not recognize strings such as 1.2.3 or 1a

Decimals with Exponents


[Font] [Default] [Show] [Resize] [History] [Profile]

School Staff ID

Write a state machine that recognises School of Computing staff ids. A School of Computing staff id must start with CS followed by one, two or three digits. The following are valid: CS66, CS109

CS staff id


[Font] [Default] [Show] [Resize] [History] [Profile]

Faculty Staff ID

Write a state machine that recognises Faculty staff ids. A Faculty staff id must start with CS or CI or BE followed by one, two or three digits. The following are valid: CS66, CI109, BE1


[Font] [Default] [Show] [Resize] [History] [Profile]

Decimals - no leading zero

This is a finite state machine that recognizes decimal numbers such as 123 and 0.123

You should not allow a leading zero unless the next character is a .

It will not recognize strings such as 0123 or 00 however it will permit 0.1

Decimal, no leading zero


[Font] [Default] [Show] [Resize] [History] [Profile]

Abstracting the FSM

You can abstract the state transition function using a HashMap of HashMaps.

For the decimal number recogniser the transition function is as follows:

A,'0' => A
A,'1' => A
A,'2' => A
A,'3' => A
A,'4' => A
A,'5' => A
A,'6' => A
A,'7' => A
A,'8' => A
A,'9' => A
A,'.' => B
B,'0' => B
B,'1' => B
...
B,'9' => B

This can be represented by the HashMap of HashMaps:

{A=>{'0'=>'A','1'=>A,'2'=>A,'3'=>A,'4'=>A,
     '5'=>'A','6'=>A,'7'=>A,'8'=>A,'9'=>A,
     '.'=>B}
 B=>{'0'=>'B','1'=>B,'2'=>B,'3'=>B,'4'=>B,
     '5'=>'B','6'=>B,'7'=>B,'8'=>B,'9'=>B}
}

Change this to include the transitions required for recognising decimals with exponents - as in question 2.

Decimals with Exponents

You might want to create a method to add a range of characters to a transition. You could then replace...

tr.put(States.A, new HashMap<Character,States>());
tr.get(States.A).put('0',States.A);
tr.get(States.A).put('1',States.A);
tr.get(States.A).put('2',States.A);
tr.get(States.A).put('3',States.A);
tr.get(States.A).put('4',States.A);
tr.get(States.A).put('5',States.A);
tr.get(States.A).put('6',States.A);
tr.get(States.A).put('7',States.A);
tr.get(States.A).put('8',States.A);
tr.get(States.A).put('9',States.A);

with

AddTransitionsRange(States.A,'0','9',States.A);



[Font] [Default] [Show] [Resize] [History] [Profile]

Augmented FSM

This is a finite state machine that strips spaces and separates words.

Decimal, no leading zero


[Font] [Default] [Show] [Resize] [History] [Profile]

Finite State Machine for String Literals

A String Literal is a double quote " followed by any sequence of characters (other than a double quote) followed by a double quote.

Acceptable string literals: "one two" and ""

Unacceptable strings one and "one

A Finite State Machine for String Literals


[Font] [Default] [Show] [Resize] [History] [Profile]