Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!caen!news.cs.indiana.edu!arizona.edu!arizona!gudeman
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: comp.lang.misc
Subject: That proof does _not_ apply to FSMs
Message-ID: <3086@optima.cs.arizona.edu>
Date: 11 May 91 22:04:15 GMT
Sender: news@cs.arizona.edu
Lines: 41

In article  <2990@optima.cs.arizona.edu> David Gudeman writes:
](I didn't want to go to this much work, but no one else has pointed
]this out, so here goes.)

It seems I didn't go to enought work.  I mumbled off the criticism
that my Paradox function is recursive:

]    Paradox = (Halt::E(Paradox)) -> CLoop ; CAccept

and then I made the mistake of sleeping on it.  On further thought, it
seems that I have to add the restriction that the encoding function E
must be restricted to ensure that descriptions of the above sort are
finite.  On even further thought, it seems that this restriction alone
takes the class of machines out of the FSMs.

Theorem:  For any class of machines C on Sigma, if there is an
encoding E : C -> Sigma* such that all C-machines M of the form

  M = M1::E(M) -> M2 ; M3

are finitely representable, then there are C-machines that can
recognize non-regular languages (which leads to the immediate that
the C-machine is not an FSA).

First, I have to add notation: CEmpty is the machine that accepts the
empty string and rejects all others.  CReject is the machine that
rejects all strings.  If the character c is Sigma, the machine c
accepts a single c and rejects any other string.  The notation M1 M2
denotes the machine that accepts all strings that are the
concatenation of any string accepted by M1 with any string accepted by
M2.  The notation M1 | M2 denotes a machine that accepts any string
accepted by either M1 or M2.

Proof: Assume that 0 and 1 are in Sigma.  The C-machine
  M = CEmpty | (0 (M:E(M) -> CAccept ; CReject) 1)
recognizes the language of n 0's followed by n 1's for any n >= 0.
This is not a regular language.
--
					David Gudeman
gudeman@cs.arizona.edu
noao!arizona!gudeman