I've been doing some work to prove some languages are not regular. I have previously used pumping lemma to prove by contradiction. However I am used to questions which ask to prove languages such as {a^n b^m| n ̸= m} ⊂ {a, b}* are not regular. I would use pumping lemma for these but now I have come across this language.
{w| w ∈ {a, b} * is not a palindrome}
I'm unsure how to prove it is irregular. Can it be done with pumping lemma? Or another method?
Extended hint/instructions:
Let $p$ be a "pumping number" (as in http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages#Formal_statement) for the language $L$ given in my prev. comment, i.e. $L$ is the language of all palindromes.
Then $w = a^p bb a^p$. Then $w \in L$. Your task is now to show that we can "pump up" $w$ in such a way that the pumped word is no longer an element of $L$.
How did I arrive at that example? The idea is that the automaton [every regular language is recognized by some DFA] can only "remember" a fixed amount (roughly corresponding to the $p$) of letters and I use a word (which is a palindrom) that is so long that the automaton can not correctly decide the property anymore, because he has "forgotten" too much.
EDIT: You should be able to do something similar for your language directly, without taking the complement.
As I said above, I would also recommend to have a look at the Myhill Nerode theorem!