Why is the below language regular?

Question

If I have a language

$$L=\left\{wxwy : w,x,y \in \{a,b\}^+ \right\}$$

I am not getting how come we are able to write regular expression for this of the form

$$a(a+b)^+ a(a+b) ^+ + b(a+b)^+ b(a+b) ^+$$

Answer 1

The point is that whenever you have a word in the language, you can assume without loss of generality that the length of the $w$ component is exactly one symbol. If somebody gives you a word with a longer $w$, you can just move all of the symbols except for the first into $x$ and $y$ instead, and get a different proof that the same word is in the language.

So you have $$ L = \{wxwy\mid x,y\in\{\mathtt a,\mathtt b\}^+, w\in\{\mathtt a,\mathtt b\}\} = \{\mathtt ax\mathtt ay\mid x,y\in\{\mathtt a,\mathtt b\}^+\} \cup \{\mathtt bx\mathtt by\mid x,y\in\{\mathtt a,\mathtt b\}^+\} $$

Answer 2

The only real restriction on $w,x$, and $y$ is that they must not be empty, so we know that every word in $L$ has at least $4$ letters. Suppose that $u\in\{a,b\}^*$ has at least $4$ letters.

Suppose that the first letter of $u$ is $a$.

• If $u=a^k$ for some $k\ge 4$, then we can let $w=x=a$ and $y=a^{k-3}$ to see that $u=a^k=aaaa^{k-3}=wxwy\in L$.

Now suppose that $u=a^kv$, where $v$ begins with $b$.

• If $v$ does not contain an $a$, then $u=a^kb^\ell$ for some $k,\ell>0$, and it’s easy to see that $u\notin L$, because it cannot be written in the form $wxwy$ with non-empty $w,x,y$.

• If the only $a$ in $v$ is its last letter, then $u=a^kb^\ell a$ for some $k,\ell>0$, and again it’s easy to see that $u\notin L$.

• If $v$ contains an $a$ that is not its last letter, we can write $u=axay$ for some non-empty strings $x$ and $y$, where the brown $a$ in $ax\color{brown}ay$ is in $v$; thus, $u\in L$.

Putting the pieces together, we see that if $u$ begins with $a$, it’s in $L$ if and only if we can decompose it as $axay$ for some $x,y\in\{a,b\}^+$, i.e., if and only if it matches the regular expression $$a(a+b)^+a(a+b)^+\;.$$

If the first letter of $u$ is $b$, you can reason similarly to show that $u\in L$ if and only if it can be decomposed as $bxby$ for some $x,y\in\{a,b\}^+$, i.e., if and only if it matches the regular expression $$b(a+b)^+b(a+b)^+\;.$$

Since $u$ must begin with one of these two letters, $L$ must correspond to the regular expression

$$a(a+b)^+a(a+b)^++b(a+b)^+b(a+b)^+\;.$$