Finite State Machines Tutorial

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

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

.

public class Decimal { public enum States {A,B,FAIL}; public static boolean fsm(String s) { States state = States.A; for (int i=0;i<s.length() && state!=States.FAIL;i++) { char c = s.charAt(i); switch (state) { case A: if (c=='.') { state = States.B; } else if (Character.isDigit(c)) { state = States.A; } else { state = States.FAIL; } break; case B: if (Character.isDigit(c)) { state = States.B; } else { state = States.FAIL; } break; default: state = States.FAIL; } } return state==States.A||state==States.B; } public static void main(String argv[]) { for(String s: new String[]{"123","0.123",".789","1.2.3","1a", "1_2","1.2_3"}) System.out.printf("%-8s %s\n",s,fsm(s)); } }

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

test text

 

 

 

 

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

Hint

• You will need to create a new state C.
• The case for B changes to allow transition to state C:

case B: if (Character.isDigit(c)) state = States.B;
        else if (c=='E') state = States.C;
        else state = States.FAIL;
        break;

• There is a similar change for A
• Any of the three states A, B and C are valid stop states. So the return statement becomes:

return state==States.A||state==States.B||state==States.C;

Decimals with Exponents

.

public class DecimalExp { public enum States {A,B,FAIL}; public static boolean fsm(String s) { States state = States.A; for (int i=0;i<s.length();i++) { char c = s.charAt(i); switch (state) { case A: if (c=='.') { state = States.B; } else if (Character.isDigit(c)) { state = States.A; } break; case B: if (Character.isDigit(c)) { state = States.B; } break; default: state = States.FAIL; } } return state==States.A||state==States.B; } public static void main(String argv[]) { for(String s: new String[]{"123","0.123",".789","1.2.3","1a", "1E8","1.2E08","1E9.0"}) { System.out.printf("%-8s %s\n",s,fsm(s)); } } }

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

test text

 

 

 

 

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

.

public class StaffID { public enum States {A,B,C,D,E,FAIL}; public static boolean fsm(String s) { States state = States.A; for (int i=0;i<s.length() && state!=States.FAIL;i++) { char c = s.charAt(i); switch (state) { case A: if (c=='C') { state = States.B; } else { state = States.FAIL; } break; case B: if (c=='S') { state = States.C; } else { state = States.FAIL; } break; case C: if (Character.isDigit(c)) { state = States.D; } else { state = States.FAIL; } break; case D: if (Character.isDigit(c)) { state = States.E; } else { state = States.FAIL; } break; default: state = States.FAIL; } } return state==States.D||state==States.E; } public static void main(String argv[]) { for(String s: new String[]{"CS111","CS66","CS5","C1","C","CS1234"}) { System.out.printf("%-8s %s\n",s,fsm(s)); } } }

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

test text

 

 

 

 

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

Hint

You only need one extra state.

.

public class StaffID { public enum States {A,B,C,D,E,F,FAIL}; public static boolean fsm(String s) { States state = States.A; for (int i=0;i<s.length() && state!=States.FAIL;i++) { char c = s.charAt(i); switch (state) { case A: if (c=='C') { state = States.B; } else { state = States.FAIL; } break; case B: if (c=='S') { state = States.C; } else { state = States.FAIL; } break; case C: if (Character.isDigit(c)) { state = States.D; } else { state = States.FAIL; } break; case D: if (Character.isDigit(c)) { state = States.E; } else { state = States.FAIL; } break; case E: if (Character.isDigit(c)) { state = States.F; } else { state = States.FAIL; } break; default: state = States.FAIL; } } return state==States.D||state==States.E||state==States.F; } public static void main(String argv[]) { for(String s: new String[]{"CS111","CI66","BE5","CE1","BS1","CS1234"}) { System.out.printf("%-8s %s\n",s,fsm(s)); } } }

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

test text

 

 

 

 

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

.

public class Decimal { public enum States {A,B,FAIL}; public static boolean fsm(String s) { States state = States.A; for (int i=0;i<s.length() && state!=States.FAIL;i++) { char c = s.charAt(i); switch (state) { case A: if (c=='.') { state = States.B; } else if (Character.isDigit(c)) { state = States.A; } else { state = States.FAIL; } break; case B: if (Character.isDigit(c)) { state = States.B; } else { state = States.FAIL; } break; default: state = States.FAIL; } } return state==States.A||state==States.B; } public static void main(String argv[]) { for(String s: new String[]{"123","0.123","08","00.3"}) { System.out.printf("%-8s %s\n",s,fsm(s)); } } }

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

test text

 

 

 

 

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);

.

import java.util.*; public class FSMbyHash { static HashMap<States,HashMap<Character,States>> tr = new HashMap<States,HashMap<Character,States>>(); public enum States {A,B,C,FAIL}; public static boolean fsm(String s) { States cur = States.A; try { for (int i=0;i<s.length() && cur!=States.FAIL;i++) { char c = s.charAt(i); cur = tr.get(cur).get(c); } return cur == States.A || cur==States.B; } catch (Exception ex) { return false; } } public static void main(String argv[]) { 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); tr.get(States.A).put('.',States.B); tr.put(States.B, new HashMap<Character,States>()); tr.get(States.B).put('0',States.A); tr.get(States.B).put('1',States.A); tr.get(States.B).put('2',States.A); tr.get(States.B).put('3',States.A); tr.get(States.B).put('4',States.A); tr.get(States.B).put('5',States.A); tr.get(States.B).put('6',States.A); tr.get(States.B).put('7',States.A); tr.get(States.B).put('8',States.A); tr.get(States.B).put('9',States.A); for(String s: new String[]{"123","0.123",".789","1.2.3","1a", "1E8","1.2E08","1E9.0"}) { System.out.printf("%-8s %s\n",s,fsm(s)); } } }

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

test text

 

 

 

 

Augmented FSM

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

.

import java.util.*; public class Words { public enum States {A,B,FAIL}; public static List<String> fsm(String s) { States state = States.A; List<String> tokens = new ArrayList<String>(); String currToken = ""; for (int i=0;i<s.length() && state!=States.FAIL;i++) { char c = s.charAt(i); switch (state) { case A: if (Character.isWhitespace(c)) { state = States.B; tokens.add(currToken); } else if (Character.isLetterOrDigit(c)) { state = States.A; } else { state = States.FAIL; } break; case B: if (Character.isWhitespace(c)) { state = States.B; } else if (Character.isLetterOrDigit(c)) { state = States.A; } else { state = States.FAIL; } break; default: state = States.FAIL; } if (state==States.A) { currToken += c; } } return tokens; } public static void main(String argv[]) { for(String s: new String[]{"one t+o th.ree four 5ive 6ix", "With 2/3 ","nix", "Sadly /* comments */ no done"}) { System.out.printf("%-8s %s\n",s,fsm(s)); } } }

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

test text

 

 

 

 

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

.

public class Hello { final static int A = 1; final static int B = 2; final static int C = 3; public static boolean fsm(String s) { int state = A; for (int i=0;i<s.length();i++) { int newState = 0; char c = s.charAt(i); switch (state) { case A: if (c=='"') { newState = B; } break; case B: if (c!='"') { newState = B; } if (c == '"') { newState = C; } break; } state = newState; } return state==C; } public static void main(String argv[]) { System.out.println(fsm("\"one two\"")); System.out.println(fsm("\"\"")); System.out.println(fsm("one")); System.out.println(fsm("\"one")); } }

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

test text