Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have this language L that contains only one string: $a_{1}a_{1}a_{2}a_{1}a_{1}a_{2}a_{3}a_{1}a_{1}a_{2}a_{1}a_{1}a_{2}a_{3} ....a_{n}...a_{n}$

written more concisely $(..(a_{1}^{2}a_{2})^{2}a_{3}^{2}..)^{2}$

I am asked to find the length of the string I found it to be $2(2^{n}-1)$ and i proved it by induction.

Now, I am asked to reduce the length of this regular expression by using the intersection operation considering that the language corresponding to $R1\bigcap R2$ is the intersection of the languages corresponding to R1 and R2, respectively.

How can I get that string by intersecting languages of different sorts using those n symbols?

share|cite|improve this question
Do you mean $$(\dots((a_1^2a_2)^2a_3)^2\dots a_{n-1})^2a_n)^2\;?$$ – Brian M. Scott Dec 13 '12 at 9:49
yes this is exactly what i meant. – J Mint Dec 13 '12 at 10:12
So if I understand your question correctly, what two string sets resulting from two shorter regular expressions can be intersected to create the equivalent of the larger regular expression which accepts exactly one string? – Neil Dec 13 '12 at 11:33
Yes i am asked to use the intersection operator to make this string( which is a regular expression) shorter by coming up with languages whom the regular expression is shorter – J Mint Dec 13 '12 at 12:12
It looks like a recursive function. I assume we can represent a regular expression using captures? – Neil Dec 13 '12 at 12:47

Your Answer


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

Browse other questions tagged or ask your own question.