Native Linux Space Warfare: Freespace 2
A Simple ISAPI Filter for Authentication on IIS
Changing Mailman Python Scripts for Virtual Host Support
Enforce Coding Standards with PHP_CodeSniffer and Eclipse IDE on Ubuntu Linux
Nice n' Easy JQuery Image Rotator
Getting Set up with Ogre 3D on Ubuntu

Finite Automata: The Theory behind Regular Expressions

Tuesday, 11 January 11, 12:27 am

Regular Expression Principles

.DotMatches every character
[]SetMatches the specified set of characters (hyphens may be used to specify a range of characters)
()BracketsGroups patterns together so they can be treated as one
|Alternativematches either the pattern to the left, or the pattern to the right
*Kleene starMatches 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.


2:30 am, Thursday, 5 May 11

Now we know who the sensible one is here. Great post!
Leave Comment

/xkcd/ Unification

About This Page