It is well established that palindrome language is non-regular. The one way to prove it is by means of pumping lemma. The other way is violating the closure properties of regular language. The strategy seems that pick a regular language and intersect with language L under consideration. If the result is a non-regular language, then L is non-regular. Can I argue that a closure properties of a non-regular language like palindrome do not form a Boolean algebra? Is it this violation that make palindrome a non-regular (context-free) language?

Moreover, please suggest some pointers where I can study palindrome language in greater detail.



Your Answer

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