I'm studying for my exam and I came across the following exam question from last year, the only way I know how to solve this is build a regex that accounts for all six different series of letters so for example to recognize a string that has the letters a,b and c occur in that order:


The question: Give a regular expression r over the alphabet A = {a, b, c} such that the language determined by r consists of all strings that contain at least one occurrence of each symbol in A. Briefly explain your answer.

  • $\begingroup$ I think an alternation of six terms of the form $a(a)*b(a+b)*c(a+b+c)*$ is easier to explain. BTW: What has been your question? $\endgroup$
    – greybeard
    Dec 28, 2019 at 16:44
  • $\begingroup$ @greybeard: yeah, i belatedly got that. I deleted my comment while thinking about how to prove that formulation in a way that justifies "easier to explain" since it seems to me that OP's formulation requires very little explanation at all. $\endgroup$
    – rici
    Dec 30, 2019 at 7:17
  • $\begingroup$ @greybeard: The big advantage of yours, it seems to me, is not ease of explanation but rather the fact that it leads to a deterministic grammar. OP's expression is a classic example of exponential state blowup of the standard regex->NFA->DFA algorithm. $\endgroup$
    – rici
    Dec 30, 2019 at 7:32

2 Answers 2


Your solution looks good to me, and it is probably what they expect of you.

It is interesting to consider the more general question: how large does a regular expression for this language be, as a function of the size of the alphabet? Denoting the size of the alphabet by $n$, Theorem 9 here shows a lower bound of $\Omega(c^n)$ for some (explicit) $c > 1$. (The theorem is for context-free grammars, but a regular expression can be translated to a context-free grammar.) Your construction is $O(n\cdot n!) = 2^{O(n\log n)}$, so there is a some gap here.

  • $\begingroup$ But cba is not in the OP’s language?! $\endgroup$ Dec 28, 2019 at 14:53
  • 1
    $\begingroup$ The regular expression in the post is only one among six different summands. Please read the post carefully. $\endgroup$ Dec 28, 2019 at 15:04
  • $\begingroup$ indeed, I suspected that to be the case, but the language was unclear enough to leave me wondering. Oh well. Were I a grader, I would have expected something more definite $\endgroup$ Dec 28, 2019 at 15:16

Spelling out the six alternatives in their most symmetrical form:
(a+b+c)* a (a+b+c)* b (a+b+c)* c (a+b+c)* +
(a+b+c)* a (a+b+c)* c (a+b+c)* b (a+b+c)* +
(a+b+c)* b (a+b+c)* a (a+b+c)* c (a+b+c)* +
(a+b+c)* b (a+b+c)* c (a+b+c)* a (a+b+c)* +
(a+b+c)* c (a+b+c)* a (a+b+c)* b (a+b+c)* +
(a+b+c)* c (a+b+c)* b (a+b+c)* a (a+b+c)*

  • 2
    $\begingroup$ Thanks for answering. However, we're not looking for answers that consist solely of an equation or regular expression; we'd like you to support your answer with explanation of how you got it or rationale or justification that it is correct. Can you edit your answer accordingly? Thank you! $\endgroup$
    – D.W.
    Dec 29, 2019 at 20:30

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.