Editing Computability (section)

=== Power of finite-state machines ===

Computer scientists call any language that can be accepted by a finite-state machine a '''[[regular language]]'''.  Because of the restriction that the number of possible states in a finite state machine is finite, we can see that to find a language that is not regular, we must construct a language that would require an infinite number of states.

An example of such a language is the set of all strings consisting of the letters 'a' and 'b' which contain an equal number of the letter 'a' and 'b'.  To see why this language cannot be correctly recognized by a finite state machine, assume first that such a machine ''M'' exists.  ''M'' must have some number of states ''n''.  Now consider the string ''x'' consisting of <math>(n+1)</math> 'a's followed by <math>(n+1)</math> 'b's.

As ''M'' reads in ''x'', there must be some state in the machine that is repeated as it reads in the first series of 'a's, since there are <math>(n+1)</math> 'a's and only ''n'' states by the [[pigeonhole principle]].  Call this state ''S'', and further let ''d'' be the number of 'a's that our machine read in order to get from the first occurrence of ''S'' to some subsequent occurrence during the 'a' sequence.  We know, then, that at that second occurrence of ''S'', we can add in an additional ''d'' (where <math>d > 0</math>) 'a's and we will be again at state ''S''.  This means that we know that a string of <math>(n+d+1)</math> 'a's must end up in the same state as the string of <math>(n+1)</math> 'a's.  This implies that if our machine accepts ''x'', it must also accept the string of <math>(n+d+1)</math> 'a's followed by <math>(n+1)</math> 'b's, which is not in the language of strings containing an equal number of 'a's and 'b's. In other words, ''M'' cannot correctly distinguish between a string of equal number of 'a's and 'b's and a string with <math>(n+d+1)</math> 'a's and <math>n+1</math> 'b's.

We know, therefore, that this language cannot be accepted correctly by any finite-state machine, and is thus not a regular language.  A more general form of this result is called the [[Pumping lemma for regular languages]], which can be used to show that broad classes of languages cannot be recognized by a finite state machine.