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, 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.