decisions. All of these are incorporated in the following definition.
Definition 2.1
A deterministic finite accepter or dfa is defined by the quintuple
M = (Q,Σ,δ,q 0 , F),
where
Q is a finite set of internal states,
Σ is a finite set of symbols called the input alphabet,
δ :Q × Σ → Q is a total function called the transition function,
q 0 ∈ Q is the initial state,
F ⊆Q is a set of final states.
A deterministic finite accepter operates in the following manner. At the
initial time, it is assumed to be in the initial state q 0 , with its input mechanism on
the leftmost symbol of the input string. During each move of the automaton, the
input mechanism advances one position to the right, so each move consumes one
input symbol. When the end of the string is reached, the string is accepted if the
automaton is in one of its final states. Otherwise the string is rejected. The input
mechanism can move only from left to right and reads exactly one symbol on
each step. The transitions from one internal state to another are governed by the
transition function δ. For example, if
δ (q 0 , a) = q 1 ,
then if the dfa is in state q 0 and the current input symbol is a, the dfa will go into
state q 1 .
In discussing automata, it is essential to have a clear and intuitive picture to
work with. To visualize and represent finite automata, we use transition graphs,
in which the vertices represent states and the edges represent transitions. The
labels on the vertices are the names of the states, while the labels on the edges
are the current values of the input symbol. For example, if q 0 and q 1 are internal
Definition 2.1
A deterministic finite accepter or dfa is defined by the quintuple
M = (Q,Σ,δ,q 0 , F),
where
Q is a finite set of internal states,
Σ is a finite set of symbols called the input alphabet,
δ :Q × Σ → Q is a total function called the transition function,
q 0 ∈ Q is the initial state,
F ⊆Q is a set of final states.
A deterministic finite accepter operates in the following manner. At the
initial time, it is assumed to be in the initial state q 0 , with its input mechanism on
the leftmost symbol of the input string. During each move of the automaton, the
input mechanism advances one position to the right, so each move consumes one
input symbol. When the end of the string is reached, the string is accepted if the
automaton is in one of its final states. Otherwise the string is rejected. The input
mechanism can move only from left to right and reads exactly one symbol on
each step. The transitions from one internal state to another are governed by the
transition function δ. For example, if
δ (q 0 , a) = q 1 ,
then if the dfa is in state q 0 and the current input symbol is a, the dfa will go into
state q 1 .
In discussing automata, it is essential to have a clear and intuitive picture to
work with. To visualize and represent finite automata, we use transition graphs,
in which the vertices represent states and the edges represent transitions. The
labels on the vertices are the names of the states, while the labels on the edges
are the current values of the input symbol. For example, if q 0 and q 1 are internal