Assignment and Answers
Examine
the FSM shown at the left. This is the same machine that was
discussed on the page Three Views
of an FSM. Recall that this FSM recognizes zero or more a's
followed by one or more b's. Now, answer the following questions:
|
| When
the machine is in state q0 is it appropriate to say that it expects
to see either an a or a b as the next input? Why
or Why not? |
 |
|
| Change
this FSM to one that recognizes 1 or more a's followed by 1 or
more b's. |
 |
|
| Define
an FSM that recognizes any sequence of a's or b's, that is, that
recognizes Sigma * |
 |
|
| If
we presented the following inputs to each of these machines,
i.e. the strings {ab, aaab,abbb,abbb,aaaabbbb} would we be able
to tell whether the machines were different or not based only
on their response to these strings, i.e, the response is either
"yes, it is accepted", namely the machine reaches its
final state when the end of the string is encountered, or the
machine hangs in some state before the end of the string is encountered. |
|
|
| Can
you define some inputs that would distinguish these machines? |
|
|
| If
we add the following tuples {<q1 b R q2>, <q2 # R qhalt>,<q2
b R q1>} to the FSM that recognizes zero or more a's followed
by 1 or more b's to define a new machine, call the first one
AB1 and this new machine AB2, then is there any input strings
that would allow you to tell them apart? |
 |
|
| Does
it take more or less states than used in AB1 to define an FSM
that recognizes exactly three a's followed by exactly two b's?
Why? |
 |
