Finite State Machines Tutorial
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
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
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
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
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
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.
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);
Augmented FSM
This is a finite state machine that strips spaces and separates words.
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