Nets, Puzzles, and Postmen by Higgins Peter M;

Author:Higgins, Peter M;
Language: eng
Format: epub
Publisher: Oxford University Press, UK
Published: 2007-03-17T16:00:00+00:00

Figure 6.6 An automaton that counts in threes

However, any particular automaton cannot count past a certain number. (The automaton of Figure 6.6 will tell you if any given number is divisible by three, but it cannot tell you the outcome of the division as it completely loses track of how many times it has looped around the cycle of states.) In fact we can give an example of an unrecognizable language and demonstrate that this is the case. Interestingly, the argument makes use of the Pigeonhole Principle, introduced in Chapter 3.

Once again, let us revert to the standard two-letter alphabet, {a, b} and let L be the language of all words of the form anbn. That is to say, L consists of all the words ab, aabb, aaabbb, … that consist of a string of a’s followed by an equal number of b’s. Suppose that A were an automaton that recognized all the words of the above language L. This much is entirely possible, but we will show that A will be forced also to accept some words not of this type, so that the language of A is not L but rather it is some larger set of words.

For each particular number n, the word an takes A from its initial state to some state that we shall denote by sn. Since anbn is accepted by A, the word bn takes A from the state sn to some accepting state, let us call it cn.

Now since A has a limited number of states but there are infinitely many possibilities for n, it follows that there must be two different numbers, m and n say, such that the states sm and sn of A are the same, even though the numbers m and n are not. With this in mind, consider the word ambn, which is not in L because m ≠ n. This word is, however, accepted by A, as am takes A from the initial state i to sm = sn, and then bn takes A from sn to the same accepting state cn, as before. As we explained above, it follows therefore that L is not the language of any automaton.

It is worth noting that the previous argument did use a version of the Pigeonhole Principle. With each number n, we associated a state of the automaton, which we called sn. In this way we are assigning an infinite number of objects (all the counting numbers) to a finite collection of pigeonholes (the states of the automaton) and so at least one state has two different numbers, m and n, assigned to it; that is to say sm = sn. Although that is all we needed in our argument, we can of course say more—at least one state will have infinitely many different numbers assigned to it. This more general observation is the basis of the famous Pumping Lemma in automata theory, which says that once an automaton accepts a word of length at least as large

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.