# Proving that $\{0^i10^i : i \ge 1\}$ is non-regular, using only closure results

I have been stumped on the following question for a few hours now, I feel like I am missing some "aha" moment.

$\text{Suppose that } \{ a^nb^n : n \ge 1 \} \text{ is non-regular.}$ $\text{Prove using closure results that } \{ 0^i10^i : i \ge 1 \} \text{ is non-regular.}$

Starting off I assumed for contradiction that the language is regular. Then I took countlessly many compliments and intersections and homomorphisms, none leading me anywhere close.

I understand using Pumping Lemma would quickly solve this problem, but the question restricts the proof technique to not using Pumping Lemma.

How would one go about solving such a question with the given restraints? Is there a methodology as to find the correct closure results to use or is it mostly intuition and luck?

• I believe this question is somewhere in our collection, but hard to find. Commented Apr 19, 2018 at 23:51

I would say that luck and intuition are improved by experience :)

The trick is also to use inverse morphisms! They can perform nondeterministic letter substitutions.

A related example. Consider the morphism $h: \{a,b\}^*\to \{0\}^*$ with $h(a) = h(b) = 0$, then $h^{-1}$ maps a word $0^n$ to any string $w\in\{a,b\}^*$ with length $n$.

Background. It is easy to write a FSA with output that maps strings $0^i10^j$ to strings $a^ib^j$, and regular languages are closed under finite state transductions (input-output transformation by two-tape finite state automaton). If you are not familiar with this result, by Nivat's Theorem: any finite state transduction can be written as a composition of an inverse morphism, intersection with regular language, and a morphism.

• I haven't really studied inverse morphisms at all, how do they defer from homomorphisms? And would the proof consist of me substituting the first set of $0$s with $i$ $a$s and the second set with $i$ $b$s and then going from there? Commented Apr 20, 2018 at 0:22
• Sorry, (homo)morphisms, are just the same concept. Commented Apr 20, 2018 at 0:33
• How about continuing from there? :/ I am still pretty stumped on how to go from $0^i10^i$ to $a^ib^i$ using inverse homomorphisms, more accurately how do I get rid of the 1? Commented Apr 20, 2018 at 2:42
• The hint is at the end of the answer: apply an inverse morphism, then intersect with a regular language, and finally apply a morphism (which will delete the $1$). I can give them explicitly, but I imagine you want your aha! moment. Commented Apr 20, 2018 at 8:37
• Is the morphism you designed valid on an input containing a 1? That is if I apply $h^{-1}(L)$ where $L$ is my language that I want to prove irregular, what would I get? Where would the 1 go? I cannot stay since the range does not contain a 1, but it also is not in the domain of the inverse morphism. Commented Apr 20, 2018 at 13:48