as expected.
Languages and Dfa's
Having made a precise definition of an accepter, we are now ready to define
formally what we mean by an associated language. The association is obvious:
The language is the set of all the strings accepted by the automaton.
Definition 2.2
The language accepted by a dfa M = (Q, Σ,δ, q 0 ,F) is the set of all strings on Σ
accepted by M. In formal notation,
Note that we require that δ, and consequently δ * , be total functions. At each
step, a unique move is defined, so that we are justified in calling such an
automaton deterministic. A dfa will process every string in Σ * and either accept it
or not accept it. Nonacceptance means that the dfa stops in a nonfinal state, so
that
Example 2.2
Consider the dfa in Figure 2.2.
In drawing Figure 2.2 we allowed the use of two labels on a single edge.
Such multiply labeled edges are shorthand for two or more distinct transitions:
The transition is taken whenever the input symbol matches any of the edge
labels.
The automaton in Figure 2.2 remains in its initial state q 0 until the first b is
encountered. If this is also the last symbol of the input, then the string is
accepted. If not, the dfa goes into state q 2 , from which it can never escape. The
state q 2 is a trap state. We see clearly from the graph that the automaton accepts
Languages and Dfa's
Having made a precise definition of an accepter, we are now ready to define
formally what we mean by an associated language. The association is obvious:
The language is the set of all the strings accepted by the automaton.
Definition 2.2
The language accepted by a dfa M = (Q, Σ,δ, q 0 ,F) is the set of all strings on Σ
accepted by M. In formal notation,
Note that we require that δ, and consequently δ * , be total functions. At each
step, a unique move is defined, so that we are justified in calling such an
automaton deterministic. A dfa will process every string in Σ * and either accept it
or not accept it. Nonacceptance means that the dfa stops in a nonfinal state, so
that
Example 2.2
Consider the dfa in Figure 2.2.
In drawing Figure 2.2 we allowed the use of two labels on a single edge.
Such multiply labeled edges are shorthand for two or more distinct transitions:
The transition is taken whenever the input symbol matches any of the edge
labels.
The automaton in Figure 2.2 remains in its initial state q 0 until the first b is
encountered. If this is also the last symbol of the input, then the string is
accepted. If not, the dfa goes into state q 2 , from which it can never escape. The
state q 2 is a trap state. We see clearly from the graph that the automaton accepts