0
$\begingroup$

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?

  • 0
    I'm just trying to determine if I can answer your question. My sincerest apologies, I won't clutter your question with commentary any longer.2012-12-14

1 Answers 1

1

I'm not sure that what you wanted but I give you a solution which is (arguably) more concise than your solution ...

Let $\Sigma$ be your alphabet. The regular expression $((..(a_1^2a_2)^2a_3)^2 ...a_n)^2$ is equivalent to: $((\Sigma\setminus\{a_n\})^*a_n)^2\bigcap_{j=2}^n ((\Sigma\setminus\{a_{j-1}\})^*a_{j-1}a_1(\Sigma\setminus\{a_{j-1}\})^*a_{j-1}a_j)^*$