Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.