Regex of 1's and 0's

I got this question which asks me to figure out "Why i开发者_Python百科s it foolish to write a regular expression for the language that consists of strings of 0's and 1's that are palindromes?" (they read the same backwards and forwards).

Part 2 of the question says that "using any formal mechanism of your choice, show how it is possible to express the language that consists of strings of 0's and 1's that are palindromes."

---

Hint: what kind of language are regular expressions designed to parse?

Since it's a homework question, I'm not going to give you a full answer - you'll learn more by working out the complete answer yourself, not to mention probably comply with whatever academic code of ethics your learning institution has. ;)

---

You need to prove the nonregularity of the language you described. There are many ways to do this, but here's a link to one method.

Scroll down to pumping lemma. This is pretty straightforward using that proof technique.

Hint: If a language can recognize binary palindromes, it can recognize 101, 11011, 1110111, ....