Use of pumping lemma in case of language $0^n 1^m$

217 Views Asked by At

It is known that language $0^n 1^m$ is regular whereas $0^n 1^n$ is not. But what if I pick string $0^p 1^p$ to proof irregularity of $0^n 1^m$ ? Here, $p$ is pumping constant. In this case, I can proof that $0^n 1^m$ is not regular. It looks to me weird but can't understand where I am wrong.

1

There are 1 best solutions below

0
On

Choosing the string $0^p1^p$ doesn't change the predicate which defines the language. Since there is no requirement that the pumped string have the form $0^n1^n$, it's trivial to pump your chosen string; just choose one of the 0's as the substring to be pumped.