# Three languages and how to decide if they are regular [closed]

From following languages which one is regular and why others are not?And what is the regular expression for regular one.

$L_1= \{wxwy | x,y,w \in (a+b)^+\}$

$L_2 = \{xwyw | x,y,w \in (a+b)^+\}$

$L_3 = \{wxyw | x,y,w \in (a+b)^+\}$

Also where can I find these type of problems?

• What have you tried and where did you get stuck? Please restrict yourself to one question per post. Where to find... why, via regular-languages of course! – Raphael Jan 22 '15 at 12:18
• According to me regular expression for them are as follows-L1={{a(a+b)^+a(a+b)^+}+{b(a+b)^+b(a+b)^+}} L2={{(a+b)^+a(a+b)^+a}+{(a+b)^+b(a+b)^+b}} L3={{a(a+b)^+(a+b)^+a}+{b(a+b)^+(a+b)^+b}} So all should be regular?Am I right or wrong?@Raphael – user1917769 Jan 22 '15 at 16:05
• What do you think? How did you get to these regular expressions? Have you tried formally proving correctness? – Raphael Jan 22 '15 at 16:13

The first two are regular, because they can be written as $aA^*aA^*+bA^*bA^*$ and $A^*aA^*a+A^*bA^*b$ (where $A=a+b$). This is because it is enough to check them for $|w|=1$, as it is implied by longer $w$.
The last language is not regular, because its intersection with the regular language $a^+b^+aba^+b^+$ is $\{a^nb^maba^nb^m| n,m\geq 1\}$ which is not regular (you can show this by pumping lemma).
• +1 This paradigm is worth mentioning, since in my experience many beginners see the first $w$ and think that it has to match the second $w$ without realizing that the important thing is that you only have to match the first characters because of the arbitrary suffixes $x$ and $y$. Good job. – Rick Decker Jan 21 '15 at 20:20
• for $L3$ I use the fact that regular language are closed under intersection. So if I nteresect $L3$ with a regular language it should stay regular. I show it is not the case for this particular language. Your expression is not correct, because for instance $abab$ is not in it. – Denis Jan 22 '15 at 11:46
• ah yes sorry, x and y have to be non empty, then say $ababab$ for instance, where $x=a$ and $y=b$. I edit the answer to correct this issue. – Denis Jan 22 '15 at 15:58