ndfaToDfa

[chris j]

Suppose our ndfa has states [0,1,2], with the following transitions:

0 '0' = 2
1 'e' = 0
1 '0' = 1

On receipt of a '0' from state 1, should you be able to go to states 0 and
1, or 0,1, and 2. According to the way the specifications are written, it
should be the epsilon closure of the set of states reachable via a '0' from
state 1, which would be only [0,1]. However, from state 1 you could 'e'
transition to state 0 and then use the '0' to transition to 2, so perhaps 2
should be included. Any thoughts? Ned?

[bushk]

i'm fairly certain the set of states accessable via a '0' transition
from state 1 in your example machine is: {2}

remember,
'0' == 'e0' == '0e' == 'e0e' == 'ee0' == ...
or as a regular expression:
e*0e*
since you can make e* w/o consuming any input.

certainly state 1 cannot be included, since you must consume a 0.
certainly state 0 cannot be included, since you must consume a 0.
certainly state 2 must be included since you can go directly (no epsilons)
the question is whether or not the path 'e0' to state 2 should be
included. i'm fairly certain it should be.

either way, however, {2} U {2} = {2}.
(1st path)(2nd path)

hope that helps.

[Nedialko B. Dimitrov]

Post by chris j
0 '0' = 2
1 'e' = 0
1 '0' = 1
On receipt of a '0' from state 1, should you be able to go to states 0 and
1, or 0,1, and 2. According to the way the specifications are written, it
should be the epsilon closure of the set of states reachable via a '0' from
state 1, which would be only [0,1]. However, from state 1 you could 'e'
transition to state 0 and then use the '0' to transition to 2, so perhaps 2
should be included. Any thoughts? Ned?

Let us say the beginning set is {1}, and the transition letter is '0'.
The specs say to first apply this letter to the set to get the set T_w.
In our case, when we do this we will get T_w={1}. Then, the specs say
to find the epsilon closure T_w. In our case, we get
epsilonclosure(T_w)={0,1}.

Ned.

[chris j]

ok cool, I guess the problem here is that we are just trying to define our
dfa differently. However, conceptually it still makes more sense to me to
include {2} (extend the definition of T_w to include the epsilon closure of
the starting state with 'char' applied). thank you though.

Post by chris j
0 '0' = 2
1 'e' = 0
1 '0' = 1
On receipt of a '0' from state 1, should you be able to go to states 0 and
1, or 0,1, and 2. According to the way the specifications are written, it
should be the epsilon closure of the set of states reachable via a '0' from
state 1, which would be only [0,1]. However, from state 1 you could 'e'
transition to state 0 and then use the '0' to transition to 2, so perhaps 2
should be included. Any thoughts? Ned?

Let us say the beginning set is {1}, and the transition letter is '0'. The
specs say to first apply this letter to the set to get the set T_w. In our
case, when we do this we will get T_w={1}. Then, the specs say to find
the epsilon closure T_w. In our case, we get epsilonclosure(T_w)={0,1}.
Ned.

[Nedialko B. Dimitrov]

Yes, the question you asked is slightly strange, because you could never
have the start set be just {1}. This is because if state 1 were in any
T_w (or epsi-closure of a T_w), state 0 would be in the epsi-closure of
that T_w as well.

Note that the start state of your DFA should be the epsi-closure of the
start state of the NDFA.

Intuitively, it is just a question of when you should eat up epsilon
transitions. You should do it as the spec suggests, after taking a
particular symbol's transitions.

Ned.

Post by chris j
ok cool, I guess the problem here is that we are just trying to define our
dfa differently. However, conceptually it still makes more sense to me to
include {2} (extend the definition of T_w to include the epsilon closure of
the starting state with 'char' applied). thank you though.

Post by chris j
0 '0' = 2
1 'e' = 0
1 '0' = 1
On receipt of a '0' from state 1, should you be able to go to states 0 and
1, or 0,1, and 2. According to the way the specifications are written, it
should be the epsilon closure of the set of states reachable via a '0' from
state 1, which would be only [0,1]. However, from state 1 you could 'e'
transition to state 0 and then use the '0' to transition to 2, so perhaps 2
should be included. Any thoughts? Ned?

Let us say the beginning set is {1}, and the transition letter is '0'. The
specs say to first apply this letter to the set to get the set T_w. In our
case, when we do this we will get T_w={1}. Then, the specs say to find
the epsilon closure T_w. In our case, we get epsilonclosure(T_w)={0,1}.
Ned.

[chris j]

I see

thanks Ned

Post by Nedialko B. Dimitrov
Yes, the question you asked is slightly strange, because you could never
have the start set be just {1}. This is because if state 1 were in any
T_w (or epsi-closure of a T_w), state 0 would be in the epsi-closure of
that T_w as well.
Note that the start state of your DFA should be the epsi-closure of the
start state of the NDFA.
Intuitively, it is just a question of when you should eat up epsilon
transitions. You should do it as the spec suggests, after taking a
particular symbol's transitions.
Ned.

Post by chris j
ok cool, I guess the problem here is that we are just trying to define our
dfa differently. However, conceptually it still makes more sense to me to
include {2} (extend the definition of T_w to include the epsilon closure of
the starting state with 'char' applied). thank you though.

Post by chris j
0 '0' = 2
1 'e' = 0
1 '0' = 1
On receipt of a '0' from state 1, should you be able to go to states 0 and
1, or 0,1, and 2. According to the way the specifications are written, it
should be the epsilon closure of the set of states reachable via a '0' from
state 1, which would be only [0,1]. However, from state 1 you could 'e'
transition to state 0 and then use the '0' to transition to 2, so
perhaps
2
should be included. Any thoughts? Ned?

Let us say the beginning set is {1}, and the transition letter is '0'. The
specs say to first apply this letter to the set to get the set T_w. In our
case, when we do this we will get T_w={1}. Then, the specs say to find
the epsilon closure T_w. In our case, we get epsilonclosure(T_w)={0,1}.
Ned.