FSA
- Finite State Automatas are built around states, and transitions
between states given inputs.
- States:once the system is in a state it stays there unless
there is an input.
- There are two special states, the start state, and the accept
states.
- Each FSA has an alphabet of inputs that it uses.
- If the system is in a state, it may transit to a new state (or
explicitly remain in the same) if there is an input.
- If the system gets to the end of the input, and it's in
a final state, it will accept the string.
- Thus, FSAs recognise languages. If a string is accepted, it's
in the language, if not it is not.
- The class of languages that is recongised by an FSA is the
Regular Lanuages
- One of the cool things about FSAs, is that
Nondeterministic Finite State Automata are Equivalent to
deterministic Finite State Automata
- If transitions are omitted, it's just assumed they go
to a sink that means not accepted.
- That is, you can have multiple transitions on a particular
input from a given state, or transit on no input.
- FSAs are used for a lot of things like tokenizers in compiler
theory, and it can be argued
that natural language is regular (though it is commonly agreed
to be at least context free).
- The FSA at the top recognizes the language a*bc.
