Prove $010010001...0^i1$ is irregular without using pumping lemma

Question

I think that we can prove it either using pigeonhole principle and a contradiction or showing that if it's regular then there's only one way to show it's DFA and since the number of states are finite and we can't make use of loops we have a contradiction. But I somehow think the latter one is pumping lemma itself so I didn't spend so much efforts on it.

Answer 1

For each $n\in\Bbb Z^+$ let $u_n=0^n1$. Let $w_1=u_1$, and for $n\in\Bbb Z^+$ let $w_{n+1}=w_nu_{n+1}$; your language is $L=\{w_n:n\in\Bbb Z^+\}$, and you can use the Myhill-Nerode theorem to prove that $L$ is not regular. I will use the terminology and notation of the article at the link.

For $w\in L$ let $[w]$ be the $R_L$-equivalence class of $w$, and let $w_m$ and $w_n$ be distinct members of $L$. Without loss of generality we may assume that $m<n$. Then $u_{m+1}$ is a distinguishing extension for $w_m$ and $w_n$, since $w_mu_{m+1}=w_{m+1}\in L$, but $w_nu_{m+1}\notin L$. Thus, $[w_n]=\{w_n\}$ for each $n\in\Bbb Z^+$, so $L$ has infinitely many $R_L$-classes and is therefore not regular.

Answer 2

If this is a regular language there exists a DFA for it. Since in the DFA's numbers of states are finite and number of strings belonging to language are infinite due to pigeonhole principle there exists a state $q_{i,j}$ in which by starting from $q_0$ we can read $w_i=01001...0^i$ and $w_j=01001...0^j$ we can reach that state. Without loss of generality we can assume that $i<j$. For reading $w_{j+1}$ first we have to read $w_j$ by reaching $q_{i,j}$ and then read $0^{j+1}1$ and reach an accepting state $q_{j+1}$. Although we can reach $q_{i,j}$ by reading $w_i$ and then read $0^{j+1}1$ and reach $q_{j+1}$ and finally read $w'=01001...0^i10^{j+1}$. Since $w'$ is not a string accepted by language we have reached a contradiction and hence $L$ is not regular.