regular expression and intersection

Question

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?

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 09:49
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 — Jiyda Moussa, 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
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. — Neil, Dec 14 '12 at 08:51

wece · Accepted Answer · 2016-10-17T15:19:21.687

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)^*$$

edited Oct 17 '16 at 15:19

answered Oct 17 '16 at 15:10

wece

2,732

regular expression and intersection

1 Answers1