Computability - Power of Automata - Power of Finite State Machines

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 'a's followed by '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 '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 ) 'a's and we will be again at state S. This means that we know that a string of 'a's must end up in the same state as the string of 'a's. This implies that if our machine accepts x, it must also accept the string of 'a's followed by '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 'a's and '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.

Read more about this topic:  Computability, Power of Automata

Famous quotes containing the words power of, machines, state, power and/or finite:

    It never was in the power of any man or any community to call the arts into being. They come to serve his actual wants, never to please his fancy.
    Ralph Waldo Emerson (1803–1882)

    Shoes are the first adult machines we are given to master.
    Nicholson Baker (b. 1957)

    An orchard, good tillage, good grounds, seem a fixture, like a gold mine, or a river, to a citizen; but to a large farmer, not much more fixed than the state of the crop.
    Ralph Waldo Emerson (1803–1882)

    No power on earth or above the bottomless pit has such influence to terrorize and make cowards of men as the liquor power. Satan could not have fallen on a more potent instrument with which to thrall the world. Alcohol is king!
    Eliza “Mother” Stewart (1816–c. 1908)

    Any language is necessarily a finite system applied with different degrees of creativity to an infinite variety of situations, and most of the words and phrases we use are “prefabricated” in the sense that we don’t coin new ones every time we speak.
    David Lodge (b. 1935)