If you want to make money online : Register now

'Quick' way to show non-regularity of languages that are 'close' to other non-regular langauges

, , No Comments
Problem Detail: 

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?

Asked By : cemulate
Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48155

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback