regular expression of 0's and 1's

Question

Hello all

I got this question which asks me to figure out why is 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 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?

Answer 1

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. ;)

Answer 2

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, ....

Answer 3

I'm just going to link to reading materials on Wikipedia:

• Chomsky hierarchy
  • Context-free grammars
  • Regular grammars
    • Regular expressions
    • Pumping lemma for regular languages