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

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