0
$\begingroup$

Question

Is $L=\left \{ wxw \,\,|\,\,w,x \,\in \left ( a+b \right )^{+}\right \}$ regular?

My Understanding/Doubt

We can say that Language

$L_{2}=\left \{ wxw \,\,|\,\,w,x \,\in \left ( a+b \right )^{*}\right \}$ is regular

By making $x=(a+b)^{*}$ and $w=\epsilon$

Based on above Understanding , i can say that $L$ is regular?


My regular expression will be-: $L=a(a+b)^{+}a+b(a+b)^{+}b+a(a+b)^{+}b+b(a+b)^{+}a$ Am i right?

$\endgroup$
0
2
$\begingroup$

When is a string of the form $a^*ba^*b$ in the language $L$, i.e., of the form $wxw$, for nonempty $w,x$?

Or, to be more explicit, what is the language $L \cap a^*ba^*b$?

$\endgroup$
3
  • $\begingroup$ your regular expression will accept $bb$ which is not in language-:$a^{0}ba^{0}b$ because $w,x$ are non empty $\endgroup$
    – laura
    Oct 6 '17 at 15:08
  • $\begingroup$ @laura It was a hint, not a solution. $\endgroup$ Oct 6 '17 at 16:04
  • $\begingroup$ sir am i right that $L$ is not regular? $\endgroup$
    – laura
    Oct 6 '17 at 16:08
0
$\begingroup$

The answer previously provided here is wrong. Counter example is $ab a ab$, see comment section below

Your conclusions are correct, but your regular expression also accepts the strings $aab$ or $abb$, which are not in $L$.

$a(a + b)^+a + b(a + b)^+b$ accepts a string $s$ if and only if $s \in L$, so $L$ is regular.

$\endgroup$
3
  • 3
    $\begingroup$ "if and only if"? What about $ab\cdot a\cdot ab$? $\endgroup$ Oct 6 '17 at 13:40
  • $\begingroup$ @HendrikJan sir, so $L$ will not be regular ? I am very confused .Please help me out $\endgroup$
    – laura
    Oct 6 '17 at 14:43
  • $\begingroup$ My answer is wrong, see Hendrick's counter example. The regular expression I provided only accepts a subset of $L$. Apologies. $\endgroup$
    – Mike B.
    Oct 7 '17 at 7:44

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