A Fuller version of FSAs
- You can do FSAs with equations, but I like diagrams especially
for simple ones. It's a directed labelled graph with nodes
being states, and arcs marking transitions.
- There is typically an unmarked failure state.
- If an arc is ommitted, it is assumed to go to the failure state,
which you can't get out of.
- (In the transition diagram from Buckland, it is assumed that you
remain in the same state.)
- You can also have non-deterministic FSAs with null transitions, and
multiple arcs for a given label. These are formally equivalent. That
is an NDFSA can be automatically converted to a DFSA.
- FSAs are used in compilers to recognise tokens (keywords like for and if,
and variable names).
- You can use prebuilt systems like YACC to build these things.
- They're really fast!
- They're also used in text mining, for quite the same reason.
- I learned about this in my second year computer science degree.
The book I used was Elements of the Theory of Computation by Lewis and
Papadimitriou. (This is one of say 10 chpts in that book.)