1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I believe this question is somewhere in our collection, but hard to find. $\endgroup$ – Hendrik Jan Apr 19 '18 at 23:51
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Ziyad Edher Apr 20 '18 at 0:22
  • $\begingroup$ Sorry, (homo)morphisms, are just the same concept. $\endgroup$ – Hendrik Jan Apr 20 '18 at 0:33
  • $\begingroup$ 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? $\endgroup$ – Ziyad Edher Apr 20 '18 at 2:42
  • 1
    $\begingroup$ 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. $\endgroup$ – Hendrik Jan Apr 20 '18 at 8:37
  • $\begingroup$ 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. $\endgroup$ – Ziyad Edher Apr 20 '18 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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