Regular expression to show that all strings contain each symbol atleast once

Problem Detail: 

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:

$(a+b+c)^*a(a+b+c)^*b(a+b+c)^*c$

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.

Asked By : Elian ten Holder

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22242