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 thelanguage determined by r consists of all strings that contain at least one occurrence of each symbol in A. Briey explain your answer.
Regular expression to show that all strings contain each symbol atleast once
regular languages;regular expressions
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.