home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1851 < prev    next >
Encoding:
Internet Message Format  |  1992-09-01  |  1020 b 
  1. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!ucbvax!CS.YALE.EDU!beigel-richard
  2. From: beigel-richard@CS.YALE.EDU (Richard Beigel)
  3. Newsgroups: comp.theory
  4. Subject: automata theory question
  5. Message-ID: <199209010003.AA02868@BEECH.THEORY.CS.YALE.EDU>
  6. Date: 1 Sep 92 19:53:52 GMT
  7. Sender: daemon@ucbvax.BERKELEY.EDU
  8. Reply-To: Richard Beigel <beigel-richard@CS.YALE.EDU>
  9. Lines: 11
  10.  
  11. We know that DPDAs can solve every decision problem that NFAs can
  12. solve, because NFAs are equivalent to DFAs.  The same does not appear
  13. to be true for function computation.  Allow NFAs and DPDAs to read a
  14. character, write a character, or perform a stack operation during each
  15. step.
  16.  
  17. Then an NFA can compute the function that maps xc to cx, for all x in
  18. {a,b}^* and all c in {a,b}.  Clearly a deterministic Turing machine
  19. can compute this function as well.  My question: Can a DPDA compute
  20. this function?  Any other candidates for a function computable by NFAs
  21. but not by DPDAs?
  22.