Drawing a NFSA with 6 States: Is it Possible?

In summary: 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?
  • #1
flying2000
40
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!
 
Physics news on Phys.org
  • #2
What do "NFA" and "NFSA" mean?
 
  • #3
it should be 'non-deterministic FSA '

non-deterministic FSA

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

http://osf1.gmu.edu/~craphae1/NFA.JPG
 
Last edited by a moderator:
  • #5
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
 
  • #6
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!

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:
  • #7
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
 
  • #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.
 
  • #9
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
 

Related to Drawing a NFSA with 6 States: Is it Possible?

1. Is it possible to draw a NFSA with 6 states?

Yes, it is possible to draw a NFSA (Non-deterministic Finite State Automaton) with 6 states. However, the complexity and feasibility of drawing a NFSA with 6 states may vary depending on the specific requirements and constraints of the system.

2. What is a NFSA and how does it differ from a DFA?

A NFSA is a type of finite state automaton that allows for non-deterministic transitions between states. Unlike a DFA (Deterministic Finite State Automaton), a NFSA can have multiple possible transitions for a given input symbol from a given state.

3. What are the key steps involved in drawing a NFSA with 6 states?

The key steps involved in drawing a NFSA with 6 states include defining the initial and final states, determining the transition table, drawing the state diagram, and testing the NFSA to ensure it meets the desired requirements.

4. How can I ensure that my drawn NFSA with 6 states is valid and efficient?

To ensure that your drawn NFSA with 6 states is valid and efficient, it is important to follow the standard rules and guidelines for drawing a NFSA. Additionally, you can use software tools and algorithms to optimize the structure and minimize the number of states in your NFSA.

5. What are some real-world applications of a NFSA with 6 states?

A NFSA with 6 states can be applied in various fields such as language processing, pattern recognition, and artificial intelligence. It can be used to model complex systems and processes that involve multiple possible outcomes or decisions. Some examples include natural language processing, speech recognition, and DNA sequence analysis.

Similar threads

  • Introductory Physics Homework Help
Replies
29
Views
1K
  • STEM Academic Advising
Replies
13
Views
1K
Replies
31
Views
2K
  • Beyond the Standard Models
Replies
13
Views
2K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
2
Views
1K
  • Introductory Physics Homework Help
Replies
17
Views
609
  • Introductory Physics Homework Help
Replies
21
Views
2K
  • Quantum Physics
Replies
24
Views
2K
  • Introductory Physics Homework Help
Replies
9
Views
1K
  • Introductory Physics Homework Help
Replies
2
Views
2K
Back
Top