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:
“Like most vigorous-minded men, seeing that there was no stopping-place between dogma and negation, he preferred to accept dogma. Of all weaknesses he most disliked timed and half-hearted faith. He would rather have jumped at once to Strong’s pure denial, than yield an inch to the argument that a mystery was to be paltered with because it could not be explained.”
—Henry Brooks Adams (1838–1918)
“The human condition is such that pain and effort are not just symptoms which can be removed without changing life itself; they are the modes in which life itself, together with the necessity to which it is bound, makes itself felt. For mortals, the “easy life of the gods” would be a lifeless life.”
—Hannah Arendt (1906–1975)