One of the most classical problems of regular expression might be the reverse of a regular language. Most solutions are based on finite state machines, that is, constructing a FSM by reversing all the arrows, adding epsilon moves to original accept states, and transforming this NFA to DFA.

However, it seems messy once you try to write down all the detail such as defining “adding epsilon moves to accept states”. Continue reading

Advertisements