Proof that palindromes are not a regular language
Here’s a simple, but effective proof that palindromes are not a regular language.
It’s known as the Myhill–Nerode theorem.
This can be proven by verifying that the check if string is a palindrome cannot be implemented using deterministic finite automaton (DFA). We will suppose that such DFA exists and then reach logical contradiction, thereby proving it cannot actually exist.
Since there is an infinite number of strings and a finite number of DFA states, there have to exist two different strings that reach the same state (this is a logical conclusion, but it’s formally known as the pigeonhole principle).
Without loss of generality, we can pick some arbitrary representations for these strings:
A = “1234”, B = “5678”
- We posited that both inputs A and B reach the same state S1 in our DFA
- By appending the same character sequence C to each string, they will both reach some state S2 (DFA has no memory of input, it just follows the transitions from S1)
- Let’s take C = “321”.
- For AC (“1234321”), end state S2 should be accepting
- For BC (“5678321”), end state S2 should be non-accepting
We reached a contradiction; S2 cannot be both accepting and non-accepting.