# Finite State Machines Tutorial

### From Progzoo

(→Augmented FSM) |
(→Augmented FSM) |
||

Line 577: | Line 577: | ||

<question className='Words' lang='java'> | <question className='Words' lang='java'> | ||

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

− | |||

− | |||

<prog><![CDATA[ | <prog><![CDATA[ | ||

− | |||

import java.util.*; | import java.util.*; | ||

## Revision as of 09:26, 2 March 2012

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.