Labs / Computer Science

Regex NFA Matcher

Type a small regular expression and it is compiled — using Thompson's construction — into a nondeterministic finite automaton. Press play and follow the glowing set of active states as each character of the test string is read. A machine can be in many states at once, and the empty (ε) arrows let it quietly branch without reading anything.

regextestshow ε

active {}reading –verdict …

What to try

Step through a(b|c)* on abcbc. At which moment is the machine sitting in several states at once, and why?
Turn off the ε arrows. Can you still tell where the "free" branching happens, or does the machine start to look deterministic?
Feed (ab)+ the string aba. Where does the active set go empty, and what does an empty set mean for the verdict?
The dot in a.c matches any single character. What is the shortest string it rejects, and the longest it accepts?
Compare 0(0|1)* against 10110. Why does a string that clearly contains the pattern still get rejected?