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?

  • 1
    Do you mean $$(\dots((a_1^2a_2)^2a_3)^2\dots a_{n-1})^2a_n)^2\;?$$2012-12-13
  • 0
    yes this is exactly what i meant.2012-12-13
  • 0
    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?2012-12-13
  • 0
    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 shorter2012-12-13
  • 0
    [It looks like a recursive function.](http://jsfiddle.net/Z9KPN/) I assume we can represent a regular expression using captures?2012-12-13
  • 0
    @Neil how may i use the function you provided?2012-12-13
  • 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)^*$$