-3
$\begingroup$

A language is defined as $w = \{ 0^m1^n \mid m, n \in \Bbb N \}$. Is this a regular language? I have seen people proving for both the sides.

Thread saying it is regular

Proof for it being non-regular

$\endgroup$

closed as off-topic by eranreches, Namaste, Shailesh, J.-E. Pin, Sahiba Arora Jan 6 '18 at 12:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – eranreches, Namaste, Shailesh, J.-E. Pin, Sahiba Arora
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 4
    $\begingroup$ The second link is for the different language where $m$ and $n$ are restricted to be unequal, so it doesn't apply here. $\endgroup$ – Daniel Schepler Jan 5 '18 at 23:33
  • $\begingroup$ Could you also help me see why adding that restriction stops it from being a regular language, I have intuition, that if you take y = 0, and pump that you might have a case where the number of 0s and 1s will be same in the string. Thanks. $\endgroup$ – Swapnil Raj Jan 5 '18 at 23:37
  • 5
    $\begingroup$ Isn't $0^*1^*$ trivially a regular expression? $\endgroup$ – Jack D'Aurizio Jan 5 '18 at 23:43
2
$\begingroup$

The language $L = \{ 0^{m}1^{n} : m, n \in \mathbb{N} \}$ is given by the regular expression $0^{*}1^{*}$, which Jack D'Aurizio pointed out.

Now the language $L^{\prime} = \{0^{m}1^{n} : m \neq n \}$ is not regular. To see this, we use the fact that regular languages are closed under the set difference operation. Suppose to the contrary that $L^{\prime}$ is regular. Then: $$0^*1^* \setminus L^{\prime} = \{ 0^{n}1^{n} : n \in \mathbb{N} \}$$

Is also regular. However, we know that $\{0^{n}1^{n} : n \in \mathbb{N} \}$ is not regular, a contradiction. So $L^{\prime}$ is not regular.

$\endgroup$

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