What information entered the process?
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.
Labs / Computer Science / Regex NFA Matcher
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.
Why it matters
Why explore this?
Computer science turns clear rules into reliable processes. This model lets you step through those rules and see how each decision changes the result.
Explore
Try the model
active {}reading –verdict …
Investigate
Questions to test
Predict first, try it in the model, then use what you observe to answer.
What to try
- Step through
a(b|c)*onabcbc. 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 stringaba. Where does the active set go empty, and what does an empty set mean for the verdict? - The dot in
a.cmatches any single character. What is the shortest string it rejects, and the longest it accepts? - Compare
0(0|1)*against10110. Why does a string that clearly contains the pattern still get rejected?
Explain
Make sense of what happened
Trace the process one step at a time. Name the rule used at each important step, then explain why the final result follows from those rules.
Check
Before you leave
Which rule changed it?
Why did the process produce this result?
If you can answer all three using evidence from the model, you understand the main idea. If not, return to Explore and change one setting at a time.