I've been reviewing past paper questions for an automaton course, and came across a question which effectively asks, which of these languages is regular? $$ \{\ 0^m1^{(m \times n)}0^n\ \colon\ m,n\ge 0\}\ $$ $$ \{\ 0^m1^{2m}0^m\ \colon\ m \geq 0\}\ $$ $$ \{\ 0^m1^n0^m\ \colon\ m\ge 0\ \&\ 0 \le n \le 1\}\ $$ $$ \{\ 0^mw\ \colon\ m\ge 0\ \&\ w \in \{0,1\}^*\ \&\ w\ \text{contains at least m 0's} \}\ $$ I have tried to apply the Pumping Lemma, but all my proofs seem to show these languages are not regular. I highly doubt the question is wrong, as the examiners' report makes not mention of it. Can anyone help be figure out which is regular?

  • 1
    $\begingroup$ In the last one, nothing requires tgat $w$ start with a $1$. Furthermore, $m$ can be $0$. So what is not part of the language? $\endgroup$
    – rici
    Commented Jan 15, 2020 at 22:33
  • $\begingroup$ Put it down to experience: Just because you have a "proof" doesn't mean it's true :-) The last one is a very simple language written in a very complicated way. $\endgroup$
    – gnasher729
    Commented Jan 15, 2020 at 22:40
  • 1
    $\begingroup$ Yeah, that last language was studied here: Is this language regular or not?. (And I had to delete my mistaken answer, six years ago.) $\endgroup$ Commented Jan 16, 2020 at 0:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.