Two levels of optional repetition yield a power set of possibilities.

If a regular expression (RE) engine uses backtracking to emulate parallelism (an NFA in the jargon) it can suffer from exponential slowdown. This page graphs the exhaustive nesting that can make a perfectly logical calculation *seem* to crash.

The regular expression we use is very reasonable: a list of comma-separated numbers. How hard can it be? The problem arises with an unexpected non-comma, here a semicolon.

If there is a match, the black line just goes right across. If there is no match, the line shows the path a regex engine might take, with backtracks in red.

Regular Expression (it’s fixed for now)

([0-9]+|,)^{✻}

Click a or type some text here and hit the tab key.

The problem arises with the nesting of two (or more) optional repetitions. Some RE engines (see below) will — quite reasonably — explore all the implications of this nesting. This results in examining all the possible ways a *sequence* (not set) can be divided into subsequences. For a sequence of N elements, there are 2^{N-1} subsequences. For this reason, it may take longer than the known lifetime of the Universe to apply such an RE to a non-matching real-world source text.

This is an example more completely dissected in Jeffrey Friedl’s articles in The Perl Journal and in his monumental, magisterial book Mastering Regular Expressions. The behavior of the tool (e.g. awk, sed, Perl, Python, etc.) when confronted with such a RE can help you distinguish between three types of RE engines:

- Fast on success, slow on failure: Traditional NFA (expect, grep, perl, python, sed)
- Fast on both: DFA (egrep, awk, lex, flex)
- Slow on both: POSIX NFA (mawk, MKS egrep, MKS lex, MKS awk)

- The Chaos Pages — A series of pages exploring iterated systems.
- The Golden Ratio Pages — A similar series of pages exploring the famous ratio.
- Gear Ratios — These may not be golden, but they are important for people who ride and work with bicycles. Available as a mobile app and a Web page.
- Anagrams — A mobile app and a Web tool for finding anagrams.
- LL(1) Parsing — A Web tool for generating a parse table and using it to construct a leftmost derivation.
- Enumeration — A Web tool for finding permutations and combinations.
- Gaussian Elimination — A Web tool for reducing matrices to row echelon form.
- Combinatorial Music Theory — A lecture connecting graph theory with musical scales and chords.
- The 3D Pages — My JavaScript implementation of interactive 3D graphics .
- The DSP Pages — Explaining the Fourier transform in the discrete domains.
- Graph Clock — A good example of using JavaScript to make a self-modifying Web page, and a little puzzle about elementary connected graphs.
- The Z-Board — A new kind of MIDI controller.