> For the homework at hand. HW1, please provide some clarification for the Finite
>State Machine
> diagram. You had previously referred to this as "FSA." What does the "A" stand for?
FSA = Finite State Automaton
> Apparently
> the lecture notes are sufficient for answering 1.2 however, your note continues to
>describe
"start"
> state and "end" state, clearly requiring us to diagram what's between those states.
>I'm quite
> certain that I'm probably making too much of this question however, how detailed
>should the
diagram
> be?
The language of sheep consists of the utterances:
"ba!"
"baa!"
"baaa!"
"baaaa!"
(etcetera)
We can model this with a regular expression (in Perl or in grep syntax):
ba+!
A FSA that recognizes this language is:
b a !
o----->o-----> o ----> o
[start] ^ \ [end]
| \
\___/
a
Reading "bab" would lead to the third state. There is no arc labeled 'b' from that
state, so the
machine stops there. And because it stops in a state that is not a final state, "bab"
is not
recognized by this machine.
Everything should be made as simple as possible, but not simpler.
(In the homework problem you don't need to draw arcs for every letter, just
label arcs with sets of valid letters.)
> Also, if this model will, in
> theory, reject entries that do not conform, should there be a "REJECT" state. or
>would that be
> handled by an "else" condition within each state?
If a string is processed (all chars read) and the machine doesn't end in the final
state, then that
string is rejected. So you don't need a separate rejection state. (In a real-life
application you
might want one or more reject states so you could get feedback about the kind of
error, but since
this is a pen-and-paper problem, you don't need that.)
> And even though it probably doesn't matter, is
> this envisioned as reading an existing file, like the comments in HW0, or is this a
>validator,
> filtering input upon entry?
It doesn't matter here.
> In the absence of attending section, I can only pose these questions to you.
>
> I guess I would like some additional grounding on these concepts/question. >Please
>advise.
Hans
