NFA with 6 states for string ending with repeated symbol

  • Thread starter Thread starter flying2000
  • Start date Start date
  • Tags Tags
    Drawing States
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
8 replies · 2K views
flying2000
Messages
40
Reaction score
0
Is that possible using six states to draw a NFSA(NFA) to represent a string ending with a symbol which occurred 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!
 

Discussion

Physics news on Phys.org
What do "NFA" and "NFSA" mean?
 
it should be 'non-deterministic FSA '

non-deterministic FSA

Tom Mattson said:
What do "NFA" and "NFSA" mean?
 
I don't see why you would even need six states

http://osf1.gmu.edu/~craphae1/NFA.JPG
 
Last edited by a moderator:
flying2000 said:
non-deterministic FSA
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.

AM
 
Thanks

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 (occurring even times). Hope we can discuss it.
Any way, thanks a lot!

so-crates said:
I don't see why you would even need six states

http://osf1.gmu.edu/~craphae1/NFA.JPG
[/URL]
 
Last edited by a moderator:
sorry.

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.

Andrew Mason said:
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.

AM
 
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.
 
flying2000 said:
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.
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?

AM