0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – Raphael Jan 22 '15 at 12:18
  • $\begingroup$ 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 $\endgroup$ – user1917769 Jan 22 '15 at 16:05
  • 1
    $\begingroup$ What do you think? How did you get to these regular expressions? Have you tried formally proving correctness? $\endgroup$ – Raphael Jan 22 '15 at 16:13
2
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ +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. $\endgroup$ – Rick Decker Jan 21 '15 at 20:20
  • $\begingroup$ I could not understand your explanation about L3.What are you assuming w,x and y as? And I think for L3 regular expression can be written as {a(a+b)^+(a+b)^+a}+{b(a+b)^+(a+b)^+b} So this should also be regular. $\endgroup$ – user1917769 Jan 22 '15 at 11:16
  • $\begingroup$ 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. $\endgroup$ – Denis Jan 22 '15 at 11:46
  • $\begingroup$ In abab what is w,x,y? And also remember x,y,w belong to (a+b)^+ so L3 length should be >=4.In abab w=a,x=b,y=a then w again can not be b $\endgroup$ – user1917769 Jan 22 '15 at 15:55
  • $\begingroup$ 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. $\endgroup$ – Denis Jan 22 '15 at 15:58

Not the answer you're looking for? Browse other questions tagged or ask your own question.