Next: Minsky's neural automata
Up: Nets with circles and
Previous: Moore machines
Contents
Index
Deterministic finitestate
automata
Deterministic finitestate automata (DFA)
(Hopcroft and Ullman (1979, 16),Salomaa (1973, 26)) may be
seen as a special case of Moore machines. A DFA is a fivetuple

(3.3) 
where , , and have the same meaning as in
Mealy and Moore machines and is the set of accepting states. If
the state reached by the DFA
after reading a complete
string in (the set of all
finitelength strings over , including the empty string
) is in then, the string is accepted; if not, the string is not accepted (or rejected). This would be
equivalent to having a
Moore machine whose output alphabet has only two symbols, Y
(yes) and N (no), and looking only at the last output symbol
(not at the whole output string) to decide
whether the string is accepted or rejected.
As an example, let
be a DFA such that:
 , , .


This automaton, which may also be represented as in figure 2.3,
accepts only those strings of 0s and 1s having an even
number of 1s. Another example of DFA is given by the following
definition

,
, .


,
,
,
,
.
This automaton, which may also be represented as in figure 2.4,
accepts only those strings of 0s and 1s not including the
substring 000.
Figure 2.3:
A deterministic finitestate automaton that accepts only binary
strings having an even number of 1s.

Figure 2.4:
A deterministic finitestate automaton that accepts only binary
strings not containing the sequence ``000''.

Next: Minsky's neural automata
Up: Nets with circles and
Previous: Moore machines
Contents
Index
Debian User
20020121