Regular Expression Artwork

For my final year university project I created a tool to visualise regular expressions. The tool visualises a set of algorithms used to compile a regular expression in to a finite state machine (very similar to a flowchart) and then use it to determine if a given string matches the regular expression.

Here are some of the images generated by the tool. In each image the left-most circle represents the start of the finite state machine (FSM) and double circles represent accepting/success states. The lines between states represent transitions and are labelled with the input character that causes the transition to be followed. In a non-deterministic FSM there are epsilon transitions that can be followed on no input. Click on any of the images to view the full size version.

Example 1 – Matching a series of digits

The following images show a non-deterministic and deterministic FSM for the regular expression (1|2|3|4|5|6|7|8|9|0)* which matches zero or more digits (0-9). The third image shows the path taken to match the input string 12486 against the regular expression.

Non-deterministic FSM for (1|2|3|4|5|6|7|8|9|0)*

Deterministic FSM for (1|2|3|4|5|6|7|8|9|0)*

Matching the string 12486 against (1|2|3|4|5|6|7|8|9|0)*

Example 2 – Matching the word hello case-insensitively

The next set of images show non-deterministic and deterministic FSMs for the regular expression (H|h)(E|e)(L|l)(L|l)(O|o) which matches the word hello using any combination of upper and lower case letters. The third image shows an optimised deterministic FSM and the fourth shows the path taken to match the string HeLlO.

Non-deterministic FSM for (H|h)(E|e)(L|l)(L|l)(O|o)

Deterministic FSM for (H|h)(E|e)(L|l)(L|l)(O|o)

Optimised deterministic FSM for (H|h)(E|e)(L|l)(L|l)(O|o)

Matching the string HeLlO against (H|h)(E|e)(L|l)(L|l)(O|o)