2.1.1 More about bombs

2.1.1.1 Palindromes do not form a regular language

You may recall that a palindrome is a string that is the same read backwards or forwards. If you ignore the spaces and the punctuation then the strings 'Madam, I'm Adam' and 'A man, a plan, a canal - Panama!' are palindromes.

(Even better: A man, a plan, a canoe, pasta, heros, rajahs, a coloratura, maps, snipe, percale, macaroni, a gag, a banana bag, a tan, a tag, a banana bag again (or a camel), a crepe, pins, Spam, a rut, a Rolo, cash, a jar, sore hats, a peon, a canal - Panama!!)

The thought-experiment swiftly persuades us that the set of palindromes over an alphabet Σ is not regular (unless Σ contains only one character of course!). After all - as you will have found by looking first at "Madam, I'm Adam" and then the two longer examples - to check whether or not a string is a palindrome one finds oneself making several passes through it, and having to compare things that are arbitrarily far apart.

Let L be the language of palindromes over {a, b}. It isn't regular, but there is no obvious bomb. However, if L were regular then so too would be the language LL(a*ba*). (The intersection of two regular languages is regular.) This new language is just the language {anbn : n ∊ ℕ}.

2.1.1.2 The language {ww : w ∊ Σ*} is not regular

I don't see how to use a bomb to show that {ww : w ∊ Σ*} is not regular, though it's obvious from the thought-experiment. However, we do know that the language L(a*b*a*b*) is regular so if our candidate were regular so too would be the language {ww : w ∊ Σ*} ∩ L(a*b*a*b*). Now this language is {anbmanbm : m, n ∊ ℕ} and it isn't hard to find bombs to explode machines purporting to recognise this language. You might like to complete the proof by finding such a bomb.



Click for answer

Next: 2.2 Kleene's theorem
Back: 2.1 Regular Expressions