Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: NFA Problem

  1. Apr 4, 2005 #1
    Is that possible using six states to draw a NFSA(NFA) to represent a string ending with a symbol which occured even times in this string(this string is consisted of only 0 and 1)..

    I thought that the regular expression is (0*10*1)*(0*10*1) + (1*01*0)*(1*01*0), It can be easy using 7 states to draw a NFSA, but I can't figure out a way only using 6 states..

    Any help wiill be appreciated!
  2. jcsd
  3. Apr 4, 2005 #2

    Tom Mattson

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What do "NFA" and "NFSA" mean?
  4. Apr 4, 2005 #3
    it should be 'non-deterministic FSA '

    non-deterministic FSA

  5. Apr 4, 2005 #4
    I don't see why you would even need six states

    http://osf1.gmu.edu/~craphae1/NFA.JPG [Broken]
    Last edited by a moderator: May 2, 2017
  6. Apr 4, 2005 #5

    Andrew Mason

    User Avatar
    Science Advisor
    Homework Helper

    Since most of us know SFA about FSA, perhaps you could expand the acronym so we can at least look it up to discover a new area of science/math that has eluded us up to now.

  7. Apr 5, 2005 #6

    U r smart! man..
    however, it seems that it only accepts the string end with 1 ocurred even times, not 0. and '01' is also accepted by it. it is not we wanted. Actually, After spending serveral nights on it. I also figure out a way using six states to accept a string end both 1 and 0 (occuring even times). Hope we can discuss it.
    Any way, thanks a lot!

    Last edited by a moderator: May 2, 2017
  8. Apr 5, 2005 #7

    sorry about that, man. But if you google 'NFSA assignment', you will find that some people name it NFSA, most call it NFA. Since My professor call it NFSA, there is nothing I can do about it and I had to follow him.

  9. Apr 6, 2005 #8
    Actually, you would need one small modification to make my NFA work... Are empty strings also part of the language ? In that case you would need an additional state.
  10. Apr 6, 2005 #9

    Andrew Mason

    User Avatar
    Science Advisor
    Homework Helper

    Thanks for the link. So how big, exactly, is this NFSA fire sprinkler? You haven't even given the pipe size. Or perhaps you are referring to a NFSA fishing line, in which case I would need the string length, wouldn't I?

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook