erh@uvacs.UUCP (03/24/84)
[]
The question is certainly interesting and very natural. Not
surprisingly, it has been investigated in depth. As a matter of fact,
the Moore theory of experiments (which is precisely the theory of
"characterizing automata from I/O pairs") was one of the subjects
investigated in the 50's which gave impetus to introduction and study
of regular languages.
A nice little book by J.H. Conway ("Regular Algebra and Finite
Machines", Chapman and Hall, 1971) has a chapter-long summary of
results including an answer to your question about the bound on the
length of the characterizing experiment. A few paraphrases:
Def. An exact (n,m,p) machine is a Moore machine with n states, m input
symbols, and p output symbols, each output symbol being actually emitted
in some state. (Take m = p = 2 if you want arguments in terms of bits.)
Theorem. Two distinguishable states of an exact (n,m,p) machine can be
distinguished by some word of length at most n-p.
(That is, for any two distinguishable states p, q, there exists a word w
of length <= n-p such that the output corresponding to w will differ
depending on whether it is started in p or q.)
Theorem. If S is a set of at most s states of an exact (n,m,p) machine,
and some two states in S are distinguishable, then there exists a word
of length at most max( 0, n-p-s+2 ) which distinguishes some two states
in S. Moreover, this bound is best possible.
Theorem. If we are (explicitely) given an exact (n,m,p) machine whose
states are all distinguishable, and told that it is initially in one
of a set S of at most s states, then we can specify an experiment of
length at most (t-1)(n-p-(t-2)/2) where t = min( s, n-p+2 ), after
application of which the resulting state will be known (so you find
your position in the machine in case you were "lost in S"). Moreover,
the bound is best possible.
In the above an "experiment of length k" means an algorithm
which feeds input symbols depending on the observed outputs; k is
the number of symbols fed in.
The following answers your question. It is a paraphrase
of Theorems 9 & 11, pp. 12-14 of Conway's text (the original result
is due to Moore, improved slightly by Conway):
Theorem. If you know that M is a strongly connected exact (n,m,p)
machine with pairwise distinguishable states, then there is an experiment
of length at most
2n-1 2
8 m n log n
2
which tells you the structure of the machine.
Ed Howorka (erh@uvacs on CSNET)