Understanding Finite State Machines: A Guide to State Tables and Functions

[prevail]

Finite state machines :(

Okay, I'm having trouble understanding a finite state machine example in my :yuck: book. It's a state table for the machine M = (S, $$\ell$$, $$\wp$$, v , $$\omega$$) where S = {S0, S1, S2}, $$\ell = \omega =$$ {0,1}.

Please check out the attachment What i don't understand is the v and $$\omega$$ column... Why is row S0; S0 in "0" and S1 in "1", and row S2; 0 in "0" and 1 in "1"?

Is this just made up or something? :tongue2:


In my textbook it says that:

v: S X $$\ell$$ -> S is the next state function
w: S X $$\ell$$ -> $$\wp$$ is the output function.. but i still don't get it :(

 

[0rthodontist]

The notation my course uses is M = (Q, Sigma, delta, q0, F) where
Q is the set of states
Sigma is the alphabet
Delta is the transition function
q0 is the start state
and F is the set of accepting states

From what you wrote it looks like l is your alphabet and you've already said v is your transition function. S looks like the set of states. I don't know what w is. P looks like it might be the set of accepting states. Please finish defining w and I might be able to help you (once the attachment is approved).

When you wrote "l = w = {0, 1}" this does not make sense to me. If l is your alphabet then only l = {0, 1}. w you defined later is a function, so it can't be {0, 1}

 

[prevail]

Hmm, my attachment is still pending. I've found the same example here :
http://www.cis.uoguelph.ca/~sawada/2910/notes/fsm-1x2.pdf (check out page 3)

 

[nocturnal]

I believe using prevail's notation that:
S is the state space
$\ell$ is the input alphabet
$\wp$ is the output alphabet
v is the next state function
and by process of elimination, $\omega$ is the initial state.

your next state function should be of the form

$v: S \times \ell \rightarrow S \times \wp$

v takes a pair consisting of the current state and input, and returns a pair consisting of the next state and output. What you did was break the next state function into two functions a funcntion v, which takes the current state and input and returns the next state, and an output function (which you mistakenly called w) which takes the current state and input and returns the output. It is often useful to do this decomposition of the next state function, but it is not part of the definition of your state machine. So w should be the initial state, and v should be given as I defined above.

 

[nocturnal]

oh... looking at page 1 of your link, they actually define a finite state machine as a 6-tuple (rather than a 5-tuple), and state what each symbol represents. Here they do break the next state function into two functions. So according to this definition your first post was correct except you didn't include the initial state in your definition. Of course I still can't see your attachment yet, so I don't know wheter the rest is correct.

 

[prevail]

oh... look at page 1 of your link. It actually defines a finite state machine as a 6-tuple (rather than a 5-tuple) and states what each symbol represents. Here they do break the next state function into two functions. So according to this definition your first post was correct except you didn't include the initial state.

Yeah, so i see But can you explain the process of "f" and "g" ? What make states:
A, column f = B and C
B, column f = B and C
C, column f = C and C

A, column g = 0 and 1
B, column g = 0 and 1
C, column g =1 and 1 ?

I just don't get it :(((

 

[nocturnal]

Yeah, so i see But can you explain the process of "f" and "g" ? What make states:
A, column f = B and C
B, column f = B and C
C, column f = C and C

A, column g = 0 and 1
B, column g = 0 and 1
C, column g =1 and 1 ?

I just don't get it :(((

I'm not sure what this means, but I think your asking how to read a table of a finite state machine. As an example consider the table given on page 2 of your link.

The first column of the table, labeled "states", refers to the current state of the state machine. The next column, f, is the next state function. The 0 and 1 sub-columns correspond to the possible inputs of 0 and 1.
The g column is the output function. The 0 and 1 sub-columns also refer to the possible inputs.

Now pretend your the finite state machine. Its given that A is the initial state so your current state is A.
Lets say you receive an input of 1. Your job is to find the next state and output.
To find the next next state, you go to column f, and look under the sub-column 1 (since that's the input), and find the entry in the same row as the current state A (row 1). You get that the next state is C.
Now, you don't switch to state C yet, the current state is still A, and you still have to find the output.
To get the output, you go to column g and look under the sub-column 1 to find the entery in the same row as the current state A (row 1). You get that the output is 1.
At this point you output a 1 and change your current state to C.
Now you wait for your next input with C as your current state.

Lets say now that you receive an input of 0. You need to find the next state and output.
To get the next state, look in column f under the sub-column 0 and find the entry in the same row as the current statem, C, in "states" (row 3). you get that the next state is C (the machine will stay in the same state).
To get the ouput, you look in column g under the sub-column 0 and get the entry in the 3rd row, which is a 1.
so now you output a 1 and your current state is C.

The process repeats ...

hope this helps.

 

[prevail]

Hmmm, I'm not sure i understod all you wrote, but thanks for your reply:)

You see one of my exercises is based on a finite state machine diagram where we're supposed to determine the output string of some input etc. , but I'm having trouble translating the diagram to a state table. My book doesn't explain this at all:( I've googled everything there is about finite state machine and i ain't getting nowhere

 

[0rthodontist]

1. Start at the start state and the first letter of the input string
2. Find v of the current state and the current letter of the input string. Now that state is where you are in the diagram. This is your new current state.
3. Output w of the start state and the (same) letter of the input string.
4. Advance to the next letter of the input string. Repeat from 2 until there are no more letters.

 

[prevail]

1. Start at the start state and the first letter of the input string
2. Find v of the current state and the current letter of the input string. Now that state is where you are in the diagram. This is your new current state.
3. Output w of the start state and the (same) letter of the input string.
4. Advance to the next letter of the input string. Repeat from 2 until there are no more letters.

Alright, now i get it. thanks for the help:)