Home

Problem Statement

You must write a program in the Python programming language that can build a Non-Deterministic Finite Automaton (NFA) from a regular expression, and can use the NFA to check if the regular expression matches any given string of text. You must write the program from scratch and cannot use the re package from the Python standard library nor any other external library.

---

Definition

In Computer Science, Thompson's construction algorithm, also called the McNaughton-Yamada-Thompson algorithm, is a method of transforming a regular expression into an equivalent Non-Deterministic Finite Automaton (NFA). This NFA can be used to match strings against the regular expression. This algorithm is credited to Ken Thompson.