Given a regular language $L$ and a regular expression $r$ with $L=L(r)$. Is it possible to determine the minimum length of words of $L(r)$ by the structure of $r$?

A straightforward example:

Let's say we have a regular expression $r=aac^*aa$, then $L(R) = \{aaaa, aacaa, aaccaa, \dots, aac^naa\}$. To determine the minimal length I would erase everything that is postfixed with $*$, leaving $r'=aaaa$. Now I would count the concatenations and add 1, which would yield in this example, not unsurprisingly, a minimum length of 4.

Is there a general approach to do this for more complex expressions?

Sidenote: I need to achieve this without the help of automata.


3 Answers 3


First, notice that you can easily eliminate $\emptyset$ for all regular expressions other than a regular expression describing the empty language. To do this, you use the following rewriting rules, which define an operator $E$ on regular expressions:

  • $E[\sigma] = \sigma$, $E[\epsilon] = \epsilon$, $E[\emptyset] = \emptyset$.
  • $E[r_1 r_2]$ is $\emptyset$ if one of $E[r_1],E[r_2]$ is $\emptyset$, and $E[r_1]E[r_2]$ otherwise.
  • $E[r_1 + r_2]$ is $E[r_1]$ if $E[r_2] = \emptyset$, $E[r_2]$ if $E[r_1] = \emptyset$, and $E[r_1] + E[r_2]$ otherwise.
  • $E[r^*] = \epsilon$ if $E[r] = \emptyset$, and $E[r]^*$ otherwise.

You can prove inductively that $E[r]$ either doesn't contain $\emptyset$, or is equal to $\emptyset$.

Applying these rewriting rules, we have either determined that the denotation of the regular expression is empty, or are given a regular expression without $\emptyset$. Now we define an operator $m$ which determines the length of the minimal word in an $\emptyset$-free regular expression:

  • $m(\sigma) = 1$, $m(\epsilon) = 0$.
  • $m(r_1r_2) = m(r_1) + m(r_2)$.
  • $m(r_1 + r_2) = \min(m(r_1),m(r_2))$.
  • $m(r^*) = 0$.

You can also implement both operators at once, by allowing $m$ to output $\infty$ (meaning that the language defined by the regular expression is empty):

  • $m(\sigma) = 1$, $m(\epsilon) = 0$, $m(\emptyset) = \infty$.
  • $m(r_1r_2) = m(r_1)+m(r_2)$, where $\infty + \ell = \ell + \infty = \infty$.
  • $m(r_1+r_2) = \min(m(r_1),m(r_2))$, where $\min(\infty,\ell) = \min(\ell,\infty) = \ell$.
  • $m(r^*) = 0$.
  • 4
    $\begingroup$ The way you handle the problem with the empty set (in the last of these equations) ls great. It seems to be an application of the tropical semiring. $\endgroup$ Nov 14, 2019 at 22:43
  • 1
    $\begingroup$ This looks promising! Thank you! $\endgroup$ Nov 18, 2019 at 7:31
  • $\begingroup$ What is $m(r_1 \times r_2)$ (the product DFA)? $\endgroup$ Oct 22, 2023 at 23:21
  • $\begingroup$ The function $m$ gets as input a regular expression, not a DFA. Moreover, semantically it gets as input a language (given as a regular expression) rather than a machine. It is a function about languages rather than about machines that decide them. $\endgroup$ Oct 29, 2023 at 13:11

The general idea from the previous answer is right but unnecessarily inefficient. Compute a NFA recognizing the regular expression. Find with BFS the shortest path from the start state to some endstate. The corresponding word is the shortest accepted word.

  • 2
    $\begingroup$ I don't think this works, since $\epsilon$-transitions contribute to the path's length but not to the word's length. You can use a weighted graph instead. If properly implemented, the complexity will be unchanged since all the weights will be in $\{0,1\}$ and all the distances in $\{0, \dots, n-1\}$, where $n$ is the number of states. $\endgroup$
    – Steven
    Nov 14, 2019 at 13:55
  • $\begingroup$ Usually NFAs (as I know them) are defined without epsilon transitions. But when considering them, you're right. However there is a method to replace those $\endgroup$
    – Daniel
    Nov 14, 2019 at 14:18
  • 2
    $\begingroup$ Yup, there is an algorithm that from a regular expression directly constructs an NFA without $\varepsilon$-transitions: Glushkov's construction, as opposed to the more common approach by Thompson that uses a lot of these transitions. (But the answer by Yuval works on expressions and avoids any explicit automata.) $\endgroup$ Nov 14, 2019 at 22:50
  • $\begingroup$ This is a handy approach, especially using a Glushkov Automaton, but unfortunately I need to do it without an automaton. Sorry, I didn't made that clear in my question! $\endgroup$ Nov 18, 2019 at 7:28

Is there a general approach to do this for more complex expressions?

Yes, there is a way. Note that a regular language is the language accepted by a NFA/DFA so the general approach to problems of this kind is to convert your expression into its corresponding NFA/DFA and then lexicographically search through all the words of the language until you find the first one that is accepted by your machine (reach the final state). I am not aware of other general methods besides this one.

  • 8
    $\begingroup$ Once you have the NFA/DFA you don't need to lexicographically search thorough all the words. It suffices to compute any shortest path from the starting state to any final state. If you have a DFA then you can just do a BFS visit. If you have a NFA then you can assign weight $0$ to $\epsilon$-transitions and weight $1$ to the other transitions. Then you can use Dijkstra's algorithm. $\endgroup$
    – Steven
    Nov 14, 2019 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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