I'm reading my textbook and I am having trouble understanding NFA's, how to convert DFA's to NFA's, and converting NFA's to regular expression. Does anyone have a very simple explanation or a good link to a site that doesn't try to explain it with big terms and mathematical symbols/variables.
![[H]ard|Forum](/styles/hardforum/xenforo/logo_dark.png){kind=logo}
NFA and DFA's
- Thread starter syn3rgyz
- Start date
nameless_centurian
Gawd
- Joined
- Apr 4, 2003
- Messages
- 836
I suggest you learn the meaning of those symbols and 'variables' as without them, you'll never be able to study any of the more interesting aspects of computer science.
I too dislike the amount of effort it takes me to learn something when all of those symbols are embedded in the process. Trust me though, I've seen too many papers that attempt to explain things without them, and the meaning is usually lost because of 1 or more of the following reasons:
1) The attempt to use descriptive wording instead of the symbols fails because at some point, the author usually gets too creative with naming things, and I don't understand his phrases.
2) The use of examples is drawn off of too heavily, so something is left out and the absence causes ambiguity, or else the examples are too simplistic or too advanced.
3) You misinterpret what the author was trying to convey by using natural language instead of well-defined symbols.
Put your time in; do it the right way. Take it from someone who has learned his lesson. Once you understand these symbols, you can rewrite the proofs and explanations in your own wording for your own personal use.
I too dislike the amount of effort it takes me to learn something when all of those symbols are embedded in the process. Trust me though, I've seen too many papers that attempt to explain things without them, and the meaning is usually lost because of 1 or more of the following reasons:
1) The attempt to use descriptive wording instead of the symbols fails because at some point, the author usually gets too creative with naming things, and I don't understand his phrases.
2) The use of examples is drawn off of too heavily, so something is left out and the absence causes ambiguity, or else the examples are too simplistic or too advanced.
3) You misinterpret what the author was trying to convey by using natural language instead of well-defined symbols.
Put your time in; do it the right way. Take it from someone who has learned his lesson. Once you understand these symbols, you can rewrite the proofs and explanations in your own wording for your own personal use.
I've spent 5 hours last night reading the explanation over and over again, and I finally understood the symbols, and what E-closure and move is. I got to the part where it explains how to convert an NFA to a DFA and it uses some kinda table. That is where I got completely lost again
It's been a while since I've studied it, but the basic idea is that with a DFA you are always in precisely one state after a given input. With a NFA, the machine has multiple simultanious states. The transformation from an NFA to a DFA simply has you create a number of new states that represent all the possible combinations of states. IE, if, after the first character, you might be in states A, C or D you create a single state ACD to represent this in your DFA. As you can see, this has the possibility to make the number of states explode.
All the complicated stuff is just figuring out which new states you need to create & doing it in a rigorous, systematic way that can proven correct.
All the complicated stuff is just figuring out which new states you need to create & doing it in a rigorous, systematic way that can proven correct.
Lord of Shadows
2[H]4U
- Joined
- Mar 9, 2004
- Messages
- 3,322
Pretty much, you create states for your DFA from the union of NDFA states you can reach. (everywhere you can go following the input symbol and any number of nondeterministic empty transitions) This union of NDFA states become your dfa state.
I learned from a course and the "Elements of the Theory of Computation" book and just recently had to go through (a|b)*aab(a|b)* for a compiler course.
You might also find this link helpful as it explains everything the program does. (Or at least it explained shift reduce parsing...)
http://www.jflap.com/tutorial/
I learned from a course and the "Elements of the Theory of Computation" book and just recently had to go through (a|b)*aab(a|b)* for a compiler course.
You might also find this link helpful as it explains everything the program does. (Or at least it explained shift reduce parsing...)
http://www.jflap.com/tutorial/
Last edited:
thanks for the link i'll check it out, but I think the part im mostly confused about is lets say there are states 0,1,2,3,4,5. If you end up with a state (2,3) and a state (3,4,5) in the DFA. And state 0 in the NFA goes to state 3 only. Then which one do you connect it to in the DFA??? (2,3)??? (3,4,5)?? or both?
Lord of Shadows
2[H]4U
- Joined
- Mar 9, 2004
- Messages
- 3,322
You might want to post an example NDFA so I can step you through it. But in that case it would go to a new state {3}, not {2,3} or {3,4,5}
Lord of Shadows
2[H]4U
- Joined
- Mar 9, 2004
- Messages
- 3,322
Your start state is zero and it can get to {0,1} because of the empty transition to state 1. So that gives us what I'll call q0.
q0 = {0,1}
So what can q0 go to on input '1'? Answer q1 = {0,1,2}
state 0: from state 0 by self transition
state 1: from state 0 by empty transition
state 2: from state 0 or state 1 by consuming input
So what can q0 go to on input '0'? Answer q2 = {0,1,5}
state 0: from state 0 by self transition
state 1: from state 0 by empty transition
state 5: from state 1 by consuming input
Where can q1 go to on input '1'? Answer q1 = {0,1,2}
state 0: from state 0 by self transition
state 1: from state 0 by empty transition
state 2: from state 0 or state 1 by consuming input
Where can q1 go to on input '0'? Answer q3 = {0,1,3,4,5}
state 0: self transition
state 1: empty transition
state 3: from state 2 consuming zero input
state 4: from state 2 consuming zero input followed by empty transition
state 5 from state 1 consuming zero input
Since state 3 and state 4 are final, this state is also final
Where can q2 go to on input '1'? Answer q4 = {0,1,2,4}
state 0: from state 0 by self transition
state 1: from state 0 by empty transition
state 2: from state 0 or state 1 by consuming input
state 4: from state 5 consuming input
Since state 4 is final, this state is also final
etc...
Sorry for the delay, was in new york.
q0 = {0,1}
So what can q0 go to on input '1'? Answer q1 = {0,1,2}
state 0: from state 0 by self transition
state 1: from state 0 by empty transition
state 2: from state 0 or state 1 by consuming input
So what can q0 go to on input '0'? Answer q2 = {0,1,5}
state 0: from state 0 by self transition
state 1: from state 0 by empty transition
state 5: from state 1 by consuming input
Where can q1 go to on input '1'? Answer q1 = {0,1,2}
state 0: from state 0 by self transition
state 1: from state 0 by empty transition
state 2: from state 0 or state 1 by consuming input
Where can q1 go to on input '0'? Answer q3 = {0,1,3,4,5}
state 0: self transition
state 1: empty transition
state 3: from state 2 consuming zero input
state 4: from state 2 consuming zero input followed by empty transition
state 5 from state 1 consuming zero input
Since state 3 and state 4 are final, this state is also final
Where can q2 go to on input '1'? Answer q4 = {0,1,2,4}
state 0: from state 0 by self transition
state 1: from state 0 by empty transition
state 2: from state 0 or state 1 by consuming input
state 4: from state 5 consuming input
Since state 4 is final, this state is also final
etc...
Sorry for the delay, was in new york.
Last edited: