How do these languages intersect the way they do?

Question

So I have these languages: $$ \begin{split} A_1 &= \{w1^{|w|}|w \in \{0,1\}^*\} \\ A_2 &= \{ww|w\in\{0,1\}^*\} \\ A_3 &= A_1 \cap A_2 \end{split} $$

$A_1$ and $A_2$ are irregular but it is said that the language described by $A_3$ is regular and is described by $A_3 = \left\{\left. 1^{2n} \right|n\in \mathbb{N} \right\}$

1. how can the intersection of two irregular languages be regular and
2. how does this intersection come about?

---

So the intersection should be: $w1^{|w|}\cap ww$, I believe that such an intersection would look like: $w1^{|w|}$ and not $1^{|w|}1^{|w|}$ or the stated $A_3 = \left\{\left. 1^{2n} \right|n\in \mathbb{N} \right\}$

Answer 1

It makes no sense to say that the intersection of $A_1$ and $A_2$ is $w1^{|w|}\cap ww$, since $w1^{|w|}$ and $ww$ are not sets of words. In fact

$$A_1\cap A_2=\left\{w\in\{0,1\}^*:\exists u,v\in\{0,1\}^*(w=u1^{|u|}=vv\right\}\;.$$

That is, $A_1\cap A_2$ is the set of binary words that can be decomposed both as $u1^{|u|}$ for some $u\in\{0,1\}^*$ and as $vv$ for some $v\in\{0,1\}^*$.

Suppose that $w=u1^{|u|}=vv$ is such a word. Let $k=|v|$; clearly

$$2k=|w|=\left|u1^{|u|}\right|=2|u|\;,$$

so $|u|=k$, and it follows immediately from $\color{red}{u}\color{blue}{1^{|u|}}=\color{red}v\color{blue}v$ that $\color{red}{u=v}$ and $\color{blue}{1^{|u|}=v}$. Thus, $v=1^k$, and $w=vv=1^{2k}$. This shows that every member of $A_1\cap A_2$ has the form $1^{2k}$ for some non-negative integer $k$, and it’s easy to check that every such word is in $A_1\cap A_2$. Thus, $A_1\cap A_2=\left\{1^{2k}\in\{0,1\}^*:k\in\Bbb N\right\}$, which of course is regular, since it is generated by the regular expression $(11)^*$.

Answer 2

I think the critical observation is that you are not constructing by intersection, but using union instead :)

This way, one piece and another piece can combine together to complete what is needed for the whole.

---

After the update on defining $A_3 = A_1 \cap A_2$, what happens is that both $A_1$ and $A_2$ are irregular, but contain a subset that is regular. That subset happens to be the same in both $A_1$ and $A_2$, so when you intersect, that subset is the only thing that is left.