|
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?
|
