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