5
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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$.
| cite | improve this answer | |
$\endgroup$
  • 3
    $\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$ – Hendrik Jan Nov 14 '19 at 22:43
  • $\begingroup$ This looks promising! Thank you! $\endgroup$ – Webastronaut Nov 18 '19 at 7:31
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 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 '19 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 '19 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$ – Hendrik Jan Nov 14 '19 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$ – Webastronaut Nov 18 '19 at 7:28
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 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 '19 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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