Converting Machines to Regular Expressions
Description
Grail+'s fmtore function converts finite state machines to regular
expressions, using the state replacement algorithm. This algorithm
tends to generate very large and redundant regular expressions, partly
because it does no simplification. In this project you will develop
and implement heuristics for simplifying regular expressions and apply
these heuristics to the problem of converting finite state
machines to regular expressions.
Tasks
- investigate current work on simplification of regular expressions
- study the expressions that tend to be generated in conversion
of finite-state machines, and characterize the types of simplification
that would be useful
- develop and implement some simplification heuristics for regular
expressions
- test the efficacy of your algorithms by using them in
the conversion of finite-state machines to regular expressions
- evaluate the cost of the simplification heuristics and develop
a metric for deciding when to use them
Difficulty
This problem is suitable for a 4th year project. It requires a student
with a good grasp of automata theory. The amount of programming required
is not large, but you should expect to run a significant number of
simulations and other experiments.
Value to the student
The project would be a useful introduction to the general problem of
developing partial solutions for a problem known to be impossible to
solve in the general case. If interesting or thoughtful heuristics
are invented, the project could easily become a Master's thesis.
Top of page
Grail+ home page