That proof does _not_ apply to FSMs 
Author Message
 That proof does _not_ apply to FSMs


](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

noao!arizona!gudeman



Thu, 28 Oct 1993 06:04:15 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. Not related, but perhaps it applies...

2. C5PE - Dictionary Field - Default Window Control not applied correctly

3. Normal order (was Logic does not apply)

4. Keywords do not apply

5. Logic does not Apply

6. Logic does not apply

7. my EXE doing not well

8. Why Forth is not doing so well

9. Not doing things

10. I'm not doing a good job

11. Relevance of lists (Was: I'm not doing a good job)

12. Using -use and -container - not quite doing what I want

 

 
Powered by phpBB® Forum Software