For any regular expression for a finite automata, how do you find the shortest word accepted?

Question

So in the question

"For the following regular expression α over the alphabet {a, b}, find one of the shortest words in the language L(α) defined by this expression"

a*abab*

As far as I understand, the answer is "aba" as this is the shortest accepted word.

What if the question instead said...

"For the following regular expressions α over the alphabet {a, b}, find one of the shortest words in {a, b}* \ L(α)"

a*abab*

What does the extra expression "{a, b}* \ L(α)" do to this question?

Answer 1

You’re correct that $aba$ is the shortest word in $L(\alpha)$. The set $\{a,b\}^*\setminus L(\alpha)$ is the set of all words in $\{a,b\}^*$ that are not in $L(\alpha)$, or in other words, all words over the alphabet $\{a,b\}$ that are not in the language $L(\alpha)$. In general, if $A$ and $B$ are any sets, $A\setminus B$ is the set of things that are in $A$ but not in $B$; you may be more familiar with it in the older notation $A-B$.

If $L(\alpha)$ is the language defined by the regular expression $a^*abab^*$, the shortest word in $\{a,b\}^*\setminus L(\alpha)$ is very short!