Accept and Generate Modes
A DFA representing a regular language can be used either in an accepting mode to validate that an input string is part of the language, or in a generating mode to generate a list of all the strings in the language.
In the accept mode an input string is provided which the automaton can read in left to right, one symbol at a time. The computation begins at the start state and proceeds by reading the first symbol from the input string and following the state transition corresponding to that symbol. The system continues reading symbols and following transitions until there are no more symbols in the input, which marks the end of the computation. If after all input symbols have been processed the system is in an accept state then we know that the input string was indeed part of the language, and it is said to be accepted, otherwise it is not part of the language and it is not accepted.
The generating mode is similar except that rather than validating an input string its goal is to produce a list of all the strings in the language. Instead of following a single transition out of each state, it follows all of them. In practice this can be accomplished by massive parallelism (having the program branch into two or more processes each time it is faced with a decision) or through recursion. As before, the computation begins at the start state and then proceeds to follow each available transition, keeping track of which branches it took. Every time the automaton finds itself in an accept state it knows that the sequence of branches it took forms a valid string in the language and it adds that string to the list that it is generating. If the language this automaton describes is infinite (ie contains an infinite number or strings, such as "all the binary string with an even number of 0s) then the computation will never halt. Given that regular languages are, in general, infinite, automata in the generating mode tends to be more of a theoretical construct.
Read more about this topic: Deterministic Finite Automaton
Famous quotes containing the words accept and/or modes:
“But the man and woman of seventy assume to know all, they have outlived their hope, they renounce aspiration, accept the actual for the necessary and talk down to the young. Let them then become organs of the Holy Ghost; let them be lovers; let them behold truth; and their eyes are uplifted, their wrinkles smoothed, they are perfumed again with hope and power.”
—Ralph Waldo Emerson (1803–1882)
“There are two modes of transport in Los Angeles: car and ambulance. Visitors who wish to remain inconspicuous are advised to choose the latter”
—Fran Lebowitz (b. 1951)