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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\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, 2018 at 0:22
  • $\begingroup$ Sorry, (homo)morphisms, are just the same concept. $\endgroup$
    – Hendrik Jan
    Apr 20, 2018 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, 2018 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, 2018 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, 2018 at 13:48

Your Answer

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

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