• Main page

1.4.1 One-step refutations using bombs

The language {aⁿbⁿ : n ∊ ℕ} is not regular

Suppose the Spiv shows us ℳ, a finite state machine that - according to him - recognises the language {aⁿ bⁿ : n ≥ 0}. The thought-experiment tells us immediately that this language is not regular so we embark on the search for a bomb with high expectations of success. In the first instance the only information we require of the Spiv is the number of states of ℳ, though we will be back later for some information about the state diagram. For the moment let k be any number such that 2k is larger than the number of states of ℳ. Think about the string a^k b^k. What does ℳ do when fed a^k b^k? It must go through a loop of course, because we have made k so large that it has to. In going through the loop it is reading a substring w of a^k b^k. What does the substring consist of? We don't know the exact answer to this, but we can narrow it down to one of the three following possibilities, and in each case we can design a bomb.

1. w consists entirely of as. Then we can take our bomb to be the string obtained from a^k by putting n copies of w instead of just one. Using our notation to the full, we can notate this string a^(k-|w|) a^(|w|·n) b^k
   Explain why this is correct.
   
   Click for the answer


2. w consists entirely of bs. Then our bomb will be the string obtained from a^k b^k by putting in several copies of w instead of just one. ℳ will accept this string, but this string contains more bs than as, and ℳ shouldn't have accepted it. Exercise: how do we notate this bomb, by analogy with the bomb in the previous case?
   
   Click for the answer


3. w consists of some as followed by some bs. In this case, when we insert n copies of w to obtain our bomb, we compel ℳ to accept a string that contains some as followed by some bs and then some as again (and then some bs). But - by saying that ℳ recognised {aⁿbⁿ : n ∊ ℕ} - the Spiv implicitly assured us that the machine would not accept any string containing as after bs. Exercise: how do we notate this bomb, by analogy with the bomb in the previous case?
   
   Click for the answer

So we know we are going to be able to make a bomb whatever w is. However, if we are required to actually exhibit a bomb we will have to require the Spiv to tell us what w is.

The language {a^kba^k : k ≥ 0} is not regular

Suppose the Spiv turns up with ℳ, a finite state machine that is alleged to recognise the language {a^kba^k : k ≥ 0}. Notice that every string in this language is a palindrome (a string that is the same read backwards as read forwards). We will show that ℳ will accept some strings that aren't palindromes, and therefore doesn't recognise {a^kba^k : k ≥ 0}.

As before, we ask the Spiv for the number of states the machine has, and get the answer m, say. Let n be any number bigger than m and consider what happens when we give ℳ the string aⁿbⁿ. This will send ℳ through a loop. That is to say, this string aⁿbⁿ has a substring within it which corresponds to the machine's passage through the loop. Call this string w. Now, since we have force-fed the machine n a's, and it has fewer than n states, it follows that w consists entirely of a's. Now we take our string aⁿbⁿ and modify it by replacing the substring w by lots of copies of itself. Any number of copies will do, as long as it's more than one. This modified string (namely a^(k+|w|)ba^k) is our bomb.

Thus ℳ accepts our bomb, thereby demonstrating - as desired - that it doesn't recognise {a^kba^k : k ≥ 0}.