Quick Introduction to Finite State Machines (FSM) or Finite State Automata (FSA)
1.1 Informal Definition
An FSA consists of
- a finite set of states,
- a set of transitions from state to state; a transition occurs on an input symbol chosen from an
alphabet.
- an initial state, that is the state in which the FSA starts; it is an element of the set of states.
- a set of final (accepting) states; that is a subset of the set of states.
- an Alphabet, that is a set of input symbols.
Example 1
An FSA which accepts all even numbers. The alphabet is the digits 0,1,2,3,4,5,6,7,8,9.
The set of states is {a,b,c}. The initial state is a. The set of final states is {b}. The set of transitions is as follows:
= in state a with input 0 or 2 or 4 or 6 or 8 go to state b.
= in state a with input 1 or 3 or 5 or 7 or 9 go to state c.
= in state c with input 0 or 2 or 4 or 6 or 8 go to state b.
= in state c with input 1 or 3 or 5 or 7 or 9 go to state c.
= in state b with input 0 or 2 or 4 or 6 or 8 go to state b.
= in state b with input 1 or 3 or 5 or 7 or 9 go to state c.
1.2 Formal Definition
An FSA is a 5-tuple (S, V, h, s0, F) where
- S is the finite set of states,
- h is an application which maps SxV to S; that is for each s in S and v in V it holds h(s,v) = s' where s' is in S.
- s0 is the initial state; it is an element of the set of states S.
- F is the set of final (accepting) states; that is a subset of the set of states S.
- V is the Alphabet, that is a set of input symbols.
Example 2
Please, reconsider example 1.
Since we will be considering the behavior of an FSA on a string of symbols of an alphabet, we have to extend the
application h to apply to a state and a string. Let W denote the set of all strings formed using an alphabet. Then,
h is an application which maps SxW to S; that is for each s in S and w = w'v in W it holds
h(s,w'v) = h(h(s,w'),v), where w' is in W.
Example 3
Based on example 2, h(a, 1234) = h( h(a, 123), 4) = ... = h( h( h( h(a, 1), 2), 3), 4) = b.
Example 4
a) Consider an FSA which recognizes numbers, e.g. 123, +1234.56E23, -231.45e-05, 432.89.
b) Consider an FSA which recognizes all positive integer numbers which are multiple of 3.
Definition 1.2 may easily be translated into a C++ program.
1.3 Deterministic FSA
An FSA (S, V, h, s0, F) is deterministic (DFSA for short) if for each s in S and each
v in V it holds that the number of states resulting from h(s,v) is at most 1;
otherwise (S, V, h, s0, F) is nondeterministic (NFSA for short).
I hope, I have kept it simple and short.
Good Luck!
Ricardo Lopez Camino
Hi, I need an easy example for understand an FSM in C++. Thanks, in advance........
Ricardo
-- To unsubscribe, email: suse-programming-e-unsubscribe@suse.com For additional commands, email: suse-programming-e-help@suse.com Archives can be found at: http://lists.suse.com/archive/suse-programming-e
-- Ebenezer Ntienjem mailto: ntienjem@netscape.net __________________________________________________________________ Introducing the New Netscape Internet Service. Only $9.95 a month -- Sign up today at http://isp.netscape.com/register Netscape. Just the Net You Need. New! Netscape Toolbar for Internet Explorer Search from anywhere on the Web and block those annoying pop-ups. Download now at http://channels.netscape.com/ns/search/install.jsp