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:
“If in the least particular one could derange the order of nature,—who would accept the gift of life?”
—Ralph Waldo Emerson (1803–1882)
“Without any extraordinary effort of genius, I have discovered that nature was the same three thousand years ago as at present; that men were but men then as well as now; that modes and customs vary often, but that human nature is always the same. And I can no more suppose, that men were better, braver, or wiser, fifteen hundred or three thousand years ago, than I can suppose that the animals or vegetables were better than they are now.”
—Philip Dormer Stanhope, 4th Earl Chesterfield (1694–1773)