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$

closed as unclear what you're asking by D.W., Luke Mathieson, Juho, David Richerby, Ellen Spertus Feb 3 '15 at 0:29

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

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