Theory of Computation (COMP314) project.
The purpose of this assignment is to write a program which will allow a regular expression and a string to be inputted. The program should recognise whether the string is a member of the language which is denoted by the regular expression.
A regular expression has to be parsed and converted to an expression tree. Using Thompson’s construction, the regular expression tree built must then be used to build an NFA accepting the language denoted by the regular expression. Using the subset construction, the NFA built must then be converted to an equivalent DFA.
Finally strings are tested to see if they are members of the language denoted by the regular expression using the DFA built.