minimization and comparison of regular expression pattern

user_1184717 0
Viewed 27

there are many ways to write a regular expression (regex) pattern that would answer the same question and yield the same result. for instance, ^aa$|^aaa$ and ^a{2,3}$ regex's patterns are equivalent in their results for the question - match all inputs that start and end with the character a and a appears either 2 or 3 times.

  1. is there an algorithm for shortening a regular expression (regex) pattern? e.g. the algorithm accepts ^aa$|^aaa$ and prints ^a{2,3}$?
  2. from theoretical perspective, when given 2 regex patterns that yield exactly the same result, would their minimized deterministic finite automaton be the same?
  3. from practical/computational perspective, when given 2 regex that yield exactly the same result, should one regex be favored over the other?
regex
1 Answers

  1. There exist algorithms to minimize a regex (depending from the metric for what you intend to minimize, e.g. regex length), but from what I've seen here, you're looking at a PSPACE-hard problem with no general solution: this and this site give different results for example.

  2. Yes, it is exactly the purpose of minimizing an automata.

  3. Yes, since they are not linked to the associated minimum automata from an implementation point of view. Here's an interesting set of examples and explainations

user_179020180
Related