2
$\begingroup$

Is there any algorithm which takes regular expression as input and finds if the regular language which expression describes is infinite?Does it have to do with pumping lemma?

Additionally,is there an algorithm which finds if a regular language of a regular expression is the empty set?

Thank you

$\endgroup$

marked as duplicate by Raphael algorithms Feb 25 '18 at 11:18

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 5
    $\begingroup$ Please don't vandalize your own question or delete it after you've already received a question. Part of our mission is to build up an archive of high-quality questions and high-quality answers that will help others in the future. When people take their time to write an answer, it is not only to help you, but also to help others who might have the same question. Deleting your question after you've gotten an answer is not fair to answerers of your question. See, e.g., meta.stackexchange.com/q/54829/160917 and meta.stackexchange.com/a/5222/160917. Thank you! $\endgroup$ – D.W. Feb 25 '18 at 4:14
  • $\begingroup$ Please ask only one question per post. (I also think that those have already been answered on the site, as they are rather popular exercise problems.) $\endgroup$ – Raphael Feb 25 '18 at 11:13
5
$\begingroup$

Yes, there is such an algorithm, and (if I am not mistaken) you can actually use a recursive evaluation of regular expressions.

Recall that regular expressions are composed from $\varnothing$, $\varepsilon$ and $a$ (for $a$ in some alphabet) using the operations $\cdot$, $+$ and $*$ (concatenation, union and iteration).

Observe that a language can only be infinite if it is based on the iteration of any language that contains a string that is not empty ($\varepsilon$). Then such an iteration can be repeatedly concatenated and unioned with other languages. The result will be infinite again, except in the case we concatenate with the empty set.

Now introduce language 'classes' NUL, ONE, FIN, and INF for the empty set, the empty string, any (finite) language that contains a string other than $\varepsilon$, and any infinite set.

Start by replacing in your regular expression any occurrence of $\varnothing$, $\varepsilon$ and $a$ by NUL, ONE and FIN respectively.

Now use a set of reductions (equalities) on the new expression, and repeat those:

  • NUL* = ONE* = ONE
  • NUL + FIN = ONE + FIN = FIN + FIN = FIN
  • NUL NUL = NUL ONE = NUL FIN = NUL INF = NUL
  • ONE FIN = FIN FIN = FIN
  • ONE INF = FIN INF = INF INF = INF
  • FIN* = INF* = INF

And many more, try to find what is needed.

And it seems to solve the empty set problem at the same time?

$\endgroup$
  • $\begingroup$ @ruakh You are right, that is not what I mean. I will edit and try to be more precise. Thanks. $\endgroup$ – Hendrik Jan Feb 25 '18 at 10:32
4
$\begingroup$

Yes, there are algorithms for both of the things you described. In fact, you can take the algorithm for the second problem and use that to produce an algorithm for the first problem. So, let's take on the second problem first.

The first thing we're going to do is convert the regular expression into an equivalent DFA. Since regular expressions and finite automata are equivalent in their descriptive power, we can always do that.

Now, consider the state diagram of the DFA we have. This is just a directed graph. Note that this DFA accepts the empty language if and only if there is no path from its start state to one of its accept states. Checking whether or not there exists a path between two vertices of a graph is very simple. Just use breadth-first search from the start state and see if some accept state is reachable.

For the first problem, we make the following observation: if the language of a DFA is finite, it can't accept any string whose length is not strictly smaller than the number of states it has. Why is this true? Well, a string with length greater than or equal to the number of states has a length greater than or equal to the pumping length of the language. So, if such a string is accepted, pumping a certain substring of that string arbitrarily many times gives us arbitrarily many strings, all of which is in our language.

Now that we have that cleared up, we can give an algorithm for the first problem. Again convert your regular expression into an equivalent DFA $M$. Let that DFA have $n$ states.

Now, construct another DFA $N$ that accepts all strings with length greater than or equal to $n$.

After that construct a DFA $P$ such that $L(P)=L(M)\cap L(N)$.

We've already established that $M$ doesn't accept any string with length greater or equal to $n$ if and only if $L(M)$ is finite. So, the only time $L(M)$ and $L(N)$ have strings in common is when $L(M)$ is infinite.

Now, use the algorithm we developed for the first problem to see if $L(P)$ is empty or not. If it is, $L(M)$ is finite. If it's not, $M$ accepts infinitely many strings and as a result, so does your regular expression.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.