8.2.  Finite State Machines

Definition 7.1 (Finite State Machine)

A FSM consists of a set of states S, a set of input symbols I, a set of end states E, a set of error states F, a action function A and a transaction function T.

S

a set of states and # of members of S < ∞, start state, and ∈ S

I

a set of input symbols and # of members of I < ∞

E

a set of end states and E ⊆ S

F

a set of error states and F ⊆ S and E ∩ F = Ø

A

a action function A with A: S × I → ``actions'' A( state, input symbol ) → action

T

a function T with T: S × I → S new_state = T( state, input symbol )

The tuple (S, I, E, F, T, A) is called a FSM.

FSM can be used to recognize patterns.

For example:

A graphical representation:

• = 0

The FSM detects also ``grumbleplan 9''!

Next iteration:

= -1

PostS plan9_2

The FSM doesn't detect ``‡‡plan 9‡. ‡ ∈ wordSeperator.

Next iteration:

= -1

The FSM detects ``‡plxplan 9‡. ‡ ∈ wordSeperator. Next iteration:

= -1

The FSM detects only ``‡plan 9‡. ‡ ∈ wordSeperator.

The definition ot the FSM:

Define a FSM which recognizes sequences of letters that have subsequences

aeiou.

For example:

--   adventitious
--   facetious
--   sacrilegious

A graphical representation:

The definition:

• Draw one FSM for the following problem:

Find the words

--   Kenya
--   Kansas
--   Kauder
--   Kunta Kinte

• Draw one FSM for the following problem:

Find the words with

--   the first letter must be an 'p'
--   the second letter must be an 'r'
--   the third letter can be an 'o' or 'e'
--   the rest ot the word is 'klap'

in an input stream.

• Draw one FSM for the following problem:

Find the words with the substring

--   Yps and
--   Ilon

in an input stream.

Last modified 22/May/97