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.


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.


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.