I am looking for kind but detailed criticism of the following chain of
reasoning, marked by the numbers. It should be clear that I am not a
student; I finished school more than ten years ago.


1. Assume we have a Turing machine M that terminates on all inputs.
2. Assume that M accepts the language L.
3. Restrict L to that subset L' which consists of all strings of L no 
   greater than length n.
4. Note that L' can be accepted by a minimal finite state machine F. 
   We require for all strings up to and including length n that F accept 
   exactly those strings in L' and reject all other strings up to and 
   including length n. We do not care, however, what other strings larger 
   than n are accepted or rejected by F.
5. Note that even if we used the configurations of M as it accepts L' 
   as states in some other finite state machine G to challenge F, 
   G could not be smaller than F because F is minimal.
6. Now let's define the regular language R which consists of all strings 
   up to and including length n.
7. There is a finite state machine R' which accepts exactly the language 
   R and rejects all other strings.
8. Now take the intersection between F and R'. Call this intersection Fmin. 
   Note that Fmin accepts L' exactly and no other strings.

I realize that the reasoning in the argument above wanders a bit and doesn't
even state a theorem to be proved, but I decided on this approach as 
a first attempt in this direction.

In order for an answer to be satisfactory, there must be a comment for every 
numbered line above, either "OK" to signify no errors in that line, or a 
detailed explanation of what is wrong. The answer must also include a brief
summary of the answerer's qualifications in the field of theoretical computer 
science. You're of course welcome to expound beyond these minimal
requirements.

I'm particularly interested in line 5, so please devote the most detail to
that line, unless, of course, it's OK.

---

Request for Question Clarification by mathtalk-ga on 30 Jan 2005 09:44 PST

Hi, anova12-ga:

I think careful analysis of a notion of minimal number of states will
require a condition on the alphabet (symbols) used by the Turing
machine.

The general pattern I'd expect is a trade-off between allowing more
symbols and requiring more states.  Of course a bare minimum is
probably the alphabet required by language L, plus the blank and a
special symbol for "halt with success".  But it is very likely that
allowing more symbols than this leads to a smaller minimum number of
states.

Recall that the action taken by the Turing machine depends on a lookup
into a table keyed by a combined current state and current symbol read
from tape.  The next state is also determined by such a lookup.

[The notion of a universal Turing machine depends heavily on the
emulation of a variable alphabet and state/action matrix by some set
alphabet and state/action matrix.  So if various encodings of L were
permitted, the number of states required could be considered bounded
above by a constant independent of L.]

I can proceed to critique the points as stated, but it would perhaps
be expeditious to clarify as much as possible the burden a "challenge"
to F by some other finite state machine is required to bear.

regards, mathtalk-ga

Dear anova12,

My qualifications are the following. I hold a B.Sc. in Computer Science
from the University of Montreal. I did well in the undergraduate
Computational Theory course and enjoyed it thoroughly. Later, as a
graduate student at the University of Waterloo, I was a teaching assistant
on two occasions for their Computational Theory course. The minimality
of deterministic finite automata (DFAs) is among my research interests,
and I have independently discovered a memory-efficient algorithm for
the incremental construction of minimal DFAs for a useful class of
languages. I feel that I have the requisite training and aptitude to
answer your question.


As per your request, I shall critique each numbered point in order.

    1. Assume we have a Turing machine M that terminates on all
    inputs.

Fine. You don't make use of the fact that M halts on all inputs in any
of the remaining points, but this is an incomplete argument by your own
admission. I'll let it pass for the time being.

    2. Assume that M accepts the language L.

Fine, although an academic would phrase it differently: "Let L be the
language accepted by M."

    3. Restrict L to that subset L' which consists of all strings
    of L no greater than length n.

This is clear, although your language is again unorthodox. The notation
could also be improved. Since the composition of L depends on the value
of n, it would be better to denote it as L_n (read "L sub n" and imagine
that n is a subscript). I would then phrase it as follows: "Let L_n be
the greatest subset of L that excludes strings of length greater than n."

    4. Note that L' can be accepted by a minimal finite state
    machine F.  We require for all strings up to and including length
    n that F accept exactly those strings in L' and reject all other
    strings up to and including length n. We do not care, however,
    what other strings larger than n are accepted or rejected by F.

First of all, I recommend that you use the name "finite automaton" (FA)
rather than "finite state machine", since the latter is non-standard
terminology that could be taken to include Turing machines. An FA, on
the other hand, is understood to be either a DFA or its close cousin,
the nondeterministic finite automaton (NFA). You may want to eventually
discuss the mechanics of the automaton, in which case you will have to
specify whether you're dealing with DFAs or NFAs. For the time being,
however, "finite automaton" will do.

I also wanted to point out that your last sentence makes an interesting
stipulation. Although it may not be immediately obvious to most readers,
the minimal FA that accepts L_n and excludes all other strings is not
necessarily the same as the minimal FA that accepts strings of length
no greater than n if they are in L_n and acts arbitrarily on strings of
length exceeding n. This is because the former is necessarily acyclic,
while the latter may contain a cycle. As an example, consider the language
{"ab", "abab"}. The minimal acyclic DFA for this language has five states,
while the minimal cyclic DFA has only three.

    5. Note that even if we used the configurations of M as it accepts
    L' as states in some other finite state machine G to challenge F,
    G could not be smaller than F because F is minimal.

There are three problems with this point. The first is your non-standard
use of the word "challenge". Although it is clear from context that you
mean it in the sense of challenging for the title of smallest FA, it
would throw off an academic reader. The second difficulty is that there
is no straightforward relationship between "the configurations of M as
it accepts" L_n and the design of an FA that accepts L_n. You should not
suggest any such relationship without specifying the exact construction.

Thirdly and finally, it is unnecessary to mention the configurations of
M at all, because they really have nothing to do with the minimality
of F. You have already stated that F is minimal, and we accept your
premise. You do not advance your argument in any way by mentioning other
FAs that are not minimal.

    6. Now let's define the regular language R which consists of
    all strings up to and including length n.

You have already defined a language L_n. Since L_n is finite, it is
necessarily regular. All finite languages are recognized by some FA and
therefore by some regular expression. Remember the Kleene construction,
which shows the equivalence of FAs and regular expressions? There is no
need to introduce a new symbol R that denotes exactly the same language
as L_n.

    7. There is a finite state machine R' which accepts exactly the
    language R and rejects all other strings.

Here we arrive at the distinction I noted earlier. Because the earlier
machine is called F, I would call this one F' and describe it as the
minimal acyclic FA that accepts L_n.

    8. Now take the intersection between F and R'. Call this
    intersection Fmin.  Note that Fmin accepts L' exactly and no
    other strings.

How do you compute the intersection of two FAs? This is an undefined
notion that you should explicitly describe if you want to use the term
"intersection". Alternatively, you could just point out the essential
differences between F and F'. If F is acyclic, then F = F'. Otherwise,
only F' is acyclic, and F' is no smaller than F.


I'm not sure exactly where this argument is headed or what it has to do
with Turing machines, but it does show promise. I am especially intrigued
by the two categories of minimal FA, one unrestricted and the other
acyclic, implied by your reasoning. If you find fault with anything I
have written above, please post a Clarification Request so that I have
the opportunity to fully meet your needs before you rate my answer.

Regards,

leapinglizard

---

Request for Answer Clarification by anova12-ga on 07 Feb 2005 21:35 PST

Hi LeapingLizard,

   Thanks for your answer. Could you provide the following 
clarifications? Thanks, anova12-ga


You note that:

 The second difficulty is that there is no straightforward relationship 
 between "the configurations of M as it accepts" L_n and the design of 
 an FA that accepts L_n. You should not suggest any such relationship 
 without specifying the exact construction.

Let's suppose I clarify it in the following manner:

Let f be a function from Turing Machines and positive integers to 
deterministic finite automata: 

          f(TM,N) = DFA

Then I rephrase point 5 to say:

5. For all f, if f(M,n) = G, then G cannot have fewer states than F
and still meet the conditions imposed on F in step 4.

Why should I have to specify the construction more precisely since
f has no hope of creating a G smaller than F because of the 
minimality of F?



You ask:
 How do you compute the intersection of two FAs? 

This is a standard construction; see the following for example:

http://www.csee.umbc.edu/~squire/cs451_l9.html


You say:

 As an example, consider the language {"ab", "abab"}. 
 The minimal acyclic DFA for this language has five states,
 while the minimal cyclic DFA has only three.

Could you specify the full transition table for the acyclic
DFA? I'm wondering how the transition function specifies the
handling of long strings. I'd also be interested in a pointer
to a good reference work on acyclic deterministic finite automata.


You note that:

 You don't make use of the fact that M halts on all inputs in any
 of the remaining points...

Correct; let me clarify that a bit. It's easy to create a TM which
goes into an infinite loop in such a way that it goes through an
infinite number of distinct configurations. An argument which tries 
to map configurations to states in a DFA would fail on such a TM. 
So I was simply trying to ensure that for the limited-length 
languages being discussed here, M would only go through a finite
number of configurations.

---

Clarification of Answer by leapinglizard-ga on 08 Feb 2005 19:12 PST

Forthwith, my responses.


    Why should I have to specify the construction more precisely
    since f has no hope of creating a G smaller than F because of
    the minimality of F?

Indeed, you have already declared F to be minimal. If you do wish to
mention other, non-minimal FAs for purposes of elucidation, it would be
best not to offer something suggestive but ultimately undefined such as
an FA that "[uses] the configurations of M as it accepts L' as states,"
since there is no obvious way to do so. You can safely leave out your
point 5 without altering the course of the argument.


        How do you compute the intersection of two FAs?

    This is a standard construction; see the following for example:

    http://www.csee.umbc.edu/~squire/cs451_l9.html

I beg to differ. It is the notion of the intersection of two languages
that is well understood. Furthermore, it is easy to construct from any two
FAs a third one that accepts the intersection of their languages. What
you are proposing, on the other hand, is the intersection of two FAs
themselves. This is quite a different notion, and one for which there
exists no standard definition. The problem is that you speak of "the
intersection between F and R'" and not of the intersection between L(F)
and L(R').

        As an example, consider the language {"ab", "abab"}.
        The minimal acyclic DFA for this language has five states,
        while the minimal cyclic DFA has only three.

    Could you specify the full transition table for the acyclic DFA?

Here you go. The start state is q0, and the accepting states are q2
and q4.

         a   b
       +--------
    q0 | q1
    q1 |     q2
    q2 | q3
    q3 |     q4
    q4 |


    I'd also be interested in a pointer to a good reference work on
    acyclic deterministic finite automata.

I don't know of any work that deals exclusively with acyclicity in
DFAs. The best introductory text on computational theory is Sipser's
Introduction to the Theory of Computation, which will tell you all about
finite automata and related matters.

Amazon: Introduction to the Theory of Computation, by Michael Sipser
http://www.amazon.com/exec/obidos/tg/detail/-/053494728X/qid=1107917965/sr=8-1/ref=sr_8_xs_ap_i1_xgl14/103-6289636-7846203?v=glance&s=books&n=507846


    So I was simply trying to ensure that for the limited-length
    languages being discussed here, M would only go through a finite
    number of configurations.

If what you mean by a configuration is a state-symbol pair, then every
Turing machine has a finite number of configurations by definition.


leapinglizard

homework

Hi, anova12-ga:

In 4 you make a point of describing F as a "minimal finite state
machine" with respect to accepting, among strings of length no more
than n, only those in L.

You then appeal to this notion of minimality in 5, although it is not
clear to what purpose you intend the comparison with some other
machine G that uses "the configurations of M."

Finally in 8 you suggestively label the "intersection" of two finite
state machines as Fmin, perhaps a further indication of an implied
claim about minimality.

Given that a notion of minimality is of real importance to your
research, a crisp way of defining it would be helpful.  Is a minimum
number of "states" intended?  Or "minimum" in some lexicographic
ordering of Turing machines?  Clearly there are a number of ways of
defining a well-order on Turing machines, and probably there some
notions that will not fit your purpose.  A notion of minimum number of
steps needed to termination would be problematic, for example.

A similar gap exists with respect to the notion of "intersection" of
two finite state machines.  For fixed n we can certainly modify any
hypothesized machine F so that it fails in n+1 steps if the input is
longer than n, but otherwise proceeds to carry out the program of the
original machine F.  The accepted strings of this modified machine
would be the "intersection" L', but you may mean something more than
this about the nature of Fmin.

regards, mathtalk-ga

Hello mathtalk-ga,

Many thanks for your helpful, patient answer. Please also
bear with me through my replies, which may contain
elementary mistakes or oversights since I'm trying to
reply within a day or two. 

By "minimality" I mean minimum number of states. 

By "intersection" I mean the FSM which accepts the set 
intersection of the languages accepted by two other FSMs.
Your construction where F fails in n+1 steps is equivalent
to what I'm trying to capture, as far as I can tell.

As for step 5, one of my goals is to show the following: if Turing
Machine M satisfies the constraints in steps 1 and 2, and
we view the configurations of M as it accepts L' as a set 
of states S, then S cannot have fewer elements than the 
set of states in F. 

Another goal is to measure the minimum amount of information 
in bits required by M to consume L'. The idea is to look at all
the outgoing transitions from a given state in an FSM: if there
are k outgoing transitions, then log(k) bits are required to
decide which transition to take. We can then add these up as
a string is consumed and the FSM goes from transition to transition,
deciding which transition to take and using information with
each decision. Now suppose we add up the bits required by F
to decide L' and come up with the answer B. If we use M to build
a FSM G which can't be smaller than F, then we ought to be able
to conclude that the number of bits required by M to consume L' is
bounded below by B.

As for Fmin, it's part of the justification for another chain of
reasoning I was planning to submit later. I was just hoping to have
the assertion in step 8 checked here.

Many thanks,

anova12-ga

Hello mathtalk-ga,

Thanks for writing. In this argument I'm only trying to deal
with a fixed L. The "challenge" is to the minimality of F while
still meeting the requirements of F in step 4. The question is:
could we use "advice" from M, or somehow watch the operation of
M, to build a G smaller than F? I'm just trying to establish that
we can't, no matter how wonderful M is.

Also, would you be willing to let me know what your qualifications
are, for my future reference?

Many thanks,

anova12-ga

Hello leapinglizard,

    Thanks for your answer. I plan to sleep on it and post a 
clarification request.

    Thanks again,

    anova12-ga