See Automata theory

Finite number of states, transitions between them are followed according to sequentially read (a.k.a. on-line) input string.

Math 574, Lesson 2-1: Finite Automata

Formally, a finite automaton on an alphabet $A$ is a tuple $(Q,I,F,E)$, where $Q$ is the set of states, the subsets of $Q$, $I$ and $F$, which are the set of input and final states, respectively. $E \subset Q \times A \times Q$ is the set of edges between states, labelled by a letter in the alphabet. The transition encoded by the edge is performed, when the automaton reads the letter, while being at the first state in the transition.

Deterministic finite automaton

Deterministic machine Reversing deterministic machines

Non-deterministic finite automaton

Non-determinstic finite state machines can have more than one transition that may be done when reading a certain input symbol on a state. They may also have epsilon transitions which can be done without reading a symbol. A string is accepted if there is at least one path through the machine that ends in an accepting state

Determinsitic equivalent in power to non-determinstic. But non-deterministic sometimes much easier to think with.

Convert non-determinsitic machine to deterministic machine

Equivalence between non-deterministic and deterministic machines is the key in proving that regular sets are closed under reversal.

To construct a FSM that accepts the complement of a regular set, just swap accepting and non-accepting states.

Closure under union key point

Closure under intersection

Why are regular sets called regular? he uses a nice heuristic explanation of the pumping lemma

See also Finite-state transducer

Build an fst on the web: http://madebyevan.com/fsm/

https://www.youtube.com/watch?v=GwsU2LPs85U