Drawing a NFSA with 6 States: Is it Possible?

[flying2000]

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!

 

[quantumdude]

What do "NFA" and "NFSA" mean?

 

[flying2000]

it should be 'non-deterministic FSA '

non-deterministic FSA

What do "NFA" and "NFSA" mean?

 

[so-crates]

I don't see why you would even need six states

http://osf1.gmu.edu/~craphae1/NFA.JPG

 

[Andrew Mason]

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

 

[flying2000]

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!

I don't see why you would even need six states

http://osf1.gmu.edu/~craphae1/NFA.JPG

[/URL]

 

[flying2000]

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.

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

 

[so-crates]

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.

 

[Andrew Mason]

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