Is it possible to reliably determine whether a given regular expression matches any string?

Question

I would like to use a regular expression for user input and determine if it matches any string, i.e. "reduce" to .+ or .* ?

I suspect that this exists , that my question will be reduced to a problem with stopping, but I would really like to make a mistake in this.

Answer 1

I do not think that what you want seems to be a Halting problem, because the grammar is regex. Given that the alphabet and language recognized by your machine are finite, you can still use a dummy algorithm that will check every world of your language and check whether its regular expression can recognize or not.

In practice, this method has terrible complexity, but you do not have any “undefined” state that you would have with the Halting problem, since the number of inputs is enumerable.

In fact, I don’t know if there is a better version of this dummy algorithm, but I hope I answered your question about the similarity to the Halting problem.