Take the language $L = \{a b^n c^n \; : \; n \geq 0\}$.

It's obvious that $L$ is non-regular because $\{b^n c^n \; : \; n \geq 0\}$ is non-regular, but I don't know a satisfying way to show that to the hypothetical Devil's advocate reading my proof without dragging out a full argument using the pumping lemma.

Is there some property of languages that can allow us to easily deduce that $L$ is non-regular if its accepted as known that $\{b^n c^n \; : \; n \geq 0\}$ is non-regular?


It is known that regular languages are closed under homomorphisms. In particular, if $L$ were regular than so would $h(L) = \{b^nc^n : n \geq 0\}$ be, where $h$ is the homomorphism given by $h(a) = \epsilon$, $h(b) = b$, $h(c) = c$. Since $h(L)$ is not regular, so is $L$ non-regular.

More generally, you can use proof by contradiction together with operations under which regular languages are closed. The idea is to start with your language, perform a bunch of operations, and end up with a non-regular language. If all operations you used preserve regularity, then you can conclude that the original language is not regular.

  • $\begingroup$ Thanks, I didn't see immediately a construction that would lead to a contradiction, but that works nicely. $\endgroup$ – cemulate Oct 12 '15 at 19:43

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.