# NFA Problem

1. Apr 4, 2005

### flying2000

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. Apr 4, 2005

### Tom Mattson

Staff Emeritus
What do "NFA" and "NFSA" mean?

3. Apr 4, 2005

### flying2000

it should be 'non-deterministic FSA '

non-deterministic FSA

4. Apr 4, 2005

### so-crates

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

5. Apr 4, 2005

### Andrew Mason

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

6. Apr 5, 2005

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

Last edited: Apr 5, 2005
7. Apr 5, 2005

### 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.

8. Apr 6, 2005

### 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.

9. Apr 6, 2005

### Andrew Mason

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