  One of the most fundamental problems in computational learning theory is the
the problem of learning a finite automaton $A$ consistent with a finite set $P$
of positive examples and with a finite set $N$ of negative examples. By
consistency, we mean that $A$ accepts all strings in $P$ and rejects all
strings in $N$. It is well known that this problem is NP-complete. In the
literature, it is stated that this NP-hardness holds even in the case of a
binary alphabet. As a standard reference for this theorem, the work of Gold
from 1978 is either cited or adapted. But as a crucial detail, the work of Gold
actually considered Mealy machines and not deterministic finite state automata
(DFAs) as they are considered nowadays. As Mealy automata are equipped with an
output function, they can be more compact than DFAs which accept the same
language. We show that the adaptions of Gold's construction for Mealy machines
stated in the literature have some issues and give a new construction for DFAs
with a binary alphabet ourselves.
