In many instances, it is of no interest to us how a particular machine is actually constructed--that is, we do not care whether a machine is made of silicon chips, wire, and steel, or whether it is constructed from tin cans, string, and matchsticks. All we want to know is what the behavioral relationship of the machine is to its defined environment. Such an abstract definition of a machine is necessary for purposes of analyzing what type of machine can achieve what end, and also to avoid dealing with the complexity of implementation at the same time as the analysis of abstract design.
Properties that are common to all machines are the processing of input and the production of output. The input may take several forms--a vending machine takes coins, an ATM takes a card, and a numeric lock takes a number punched on a keypad. Output can also correspondingly take many forms. Although the inputs and outputs for real machines are often seen to consist of real entities such as coins or cards, in theoretical analyses it is common to consider machines as operating on strings of data in a specified formal language with a fixed alphabet. A machine is then thought to be a language acceptor that accepts certain well-formed strings in the input alphabet it is designed to work with. It is important in this context to understand that 'language' here does not mean English or any other human language, nor even computer or programming language; we use the term merely as an abstraction for understanding the input and output behavior of machines.
The finite-state machine is a formal definition of an abstract machine, and is concerned only with the internal states that the machine goes through as it processes symbols in its input alphabet. A sequence of valid symbols in the language of the machine may cause it to transition to a state where it produces a desired output.
For instance, a familiar vending machine that produces a can of soda upon receiving 50 cents may be thought of as an implementation of a finite-state machine with the following states:
Initial state--before any coins have been inserted.
"Needs 45 cents"--the state after a nickel is inserted.
"Needs 40 cents"--the state after a dime, or two nickels have been inserted.
"Needs 35 cents"--the state after three nickels, or a dime and a nickel, have been inserted.
"Needs 30 cents"--the state after four nickels, or two dimes, or other combinations, have been inserted.
"Needs 25 cents"--the state after five nickels, or a combination of dimes and nickels, or a quarter, have been inserted.
"Needs 20 cents"--the state after six nickels, or three dimes, or a combination of dimes and nickels, or a quarter and a nickel, have been inserted.
"Needs 15 cents"--the state after seven nickels, or three dimes and a nickel, or a quarter and a dime, have been inserted.
"Needs 10 cents"--the state after eight nickels, or four dimes, or a combination, or a quarter and a dime and a nickel, have been inserted.
"Needs 5 cents"--the state after nine nickels, or two dimes and a quarter, or other combinations, have been inserted.
Output state--after 50 cents are inserted; a can is output.
The physical vending machine may be thought of as an instantiation of a finite state machine with these eleven states. Each coin may be thought of as a symbol in the alphabet of the finite state machine, and with each valid symbol that is input, the machine transitions to another state, until finally the desired output state is reached. If a symbol that is not in the alphabet used by the machine is input, then the machine's state may be undefined, or it may stay in the current state. For example, if the soda machine is given coins in foreign currency, or pennies, which are not valid inputs, then it may either return error messages, or may just ignore the inputs.
A finite-state machine is often represented by a labeled directed graph, also called a state diagram. The nodes of the state diagram are states of the machine, such as described above. Arcs between the nodes describe the transitions between states, and the arcs are labeled by the input that causes the corresponding transition. For instance, in case of a state diagram for the vending machine example above, we could have an arc from the state "Needs 25 cents" to the Output state labeled "quarter." The machine is considered to be a language acceptor for certain valid strings in its language--for instance, the vending machine we have described is an acceptor for the language of all input strings where the sum of the values of the coins is 50 cents. Machines that accept the same language are considered equivalent, even if they are implemented differently.
More generally, a finite-state machine may have more than one defined initial state, and more than one possible terminal state. (For example, many vending machines can deliver both chips and candy bars.)
This is the complete article, containing 818 words
(approx. 3 pages at 300 words per page).
