Regular Expression Principles

.	Dot	Matches every character
[]	Set	Matches the specified set of characters (hyphens may be used to specify a range of characters)
()	Brackets	Groups patterns together so they can be treated as one
|	Alternative	matches either the pattern to the left, or the pattern to the right
*	Kleene star	Matches any number of repetitions of the pattern to the left (even none)

While there are additional constructs available in most Regular Expression syntaxes, the above are sufficient to express all Regular Expressions; the additional constructs are in effect merely shorthand ways to express more complicated patterns. For instance, the + operator, meaning 1 or more repetitions of the pattern to its left, is equivalent to writing the pattern to match once, and then once again with a Kleene star. For instance, [a-f]+ is just a more terse way to write [a-f][a-f]*.

Finite Automata

Finite Automata, or finite state machines, are machines which predictably change state from one of a finite set of states to another according to a specific event. A graph depicting what events lead from one state to another is called a state transition diagram. Any device which can be in finitely many states and which changes from one state to another deterministically is a finite automaton, and its behaviour can be completely described by a state transition diagram.