# How to determine minimum word length of regular language

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.

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$$.
• 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. – Hendrik Jan Nov 14 '19 at 22:43
• This looks promising! Thank you! – Webastronaut Nov 18 '19 at 7:31

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.

• 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. – Steven Nov 14 '19 at 13:55
• 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 – Daniel Nov 14 '19 at 14:18
• 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.) – Hendrik Jan Nov 14 '19 at 22:50
• 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! – Webastronaut Nov 18 '19 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.

• 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. – Steven Nov 14 '19 at 13:53