0
$\begingroup$

L = { x^n y^n / x,y belongs to (a+b)^* , number of a's in x = number of b's in y and n > 0}

According to me it's regular because for any string $w$ belongs to $(a+b)^*$, we can divide the string into 2 parts $x$ and $y$ with $n=1$ .

Is my reasoning correct?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Your reasoning is quite incomplete. It doesn't constitute a proof. It doesn't explain why you can divide any string $w$ into two parts $x$ and $y$. $\endgroup$
    – Yuval Filmus
    Commented Nov 11, 2017 at 20:55
  • $\begingroup$ I just took many examples and noticed that for any string w, it can be divided into parts x and y. Like aaabbbaa into aaa (x) , bbbaaa(y). $\endgroup$
    – Ramesh
    Commented Nov 11, 2017 at 21:17
  • 1
    $\begingroup$ That's fine, but how do you know that it's the case for all words? You need to prove it! $\endgroup$
    – Yuval Filmus
    Commented Nov 11, 2017 at 21:41
  • 1
    $\begingroup$ Still better, let someone else prove it: Is language $\{a,b\}^∗$ same as language $\{xy\in \{a,b\}^∗\mid |x|_a=|y|_b\}$? $\endgroup$
    – Hendrik Jan
    Commented Nov 11, 2017 at 21:51
  • $\begingroup$ @Hendrik Jan, Thanks for the link. So I think even this language is regular. We need to just put n=1. $\endgroup$
    – Ramesh
    Commented Nov 12, 2017 at 3:28

0

Reset to default

Browse other questions tagged or ask your own question.