regex to ndfa

[alex cheng]

Ok, here is my interpretation of what an ndfa should look like, if given a
regex. Feel free to agree or disagree.

EmptySet = ([0], 0, [], no transitions)

Epsilon = ([0], 0, [0], no transitions)

Symb '0' = ([0,1], 0, [1], only transition is from 0 to 1 on receipt of '0')

Let me know what you think.
-chris

[bushk]

yes.

epsilon also could be = ([0], 0, [0], delta)
where
delta 0 'e' = [0]
but epsilon transitions to themselves are effectively moot.

a good way to test if your machines are right is to test if Star
EmptySet is an quivilent machine to Epsilon.

[Danny Hoodin]

Couldn't Epsilon be
([0,1],1,[1],eTrans)
where eTrans 0 'e' = [1]

This would work exactly the same (ie it would accept the correct
language), but would have one extra state in any ndfa that had epsilon.
Does that make it incorrect?

Post by alex cheng
Ok, here is my interpretation of what an ndfa should look like, if given a
regex. Feel free to agree or disagree.
EmptySet = ([0], 0, [], no transitions)
Epsilon = ([0], 0, [0], no transitions)
Symb '0' = ([0,1], 0, [1], only transition is from 0 to 1 on receipt of '0')
Let me know what you think.
-chris

[Scott Kilpatrick]

Or you could use the epsilon machine that is given in the utilities.hs
file... one and zero too.

Scotto

Post by Danny Hoodin
Couldn't Epsilon be
([0,1],1,[1],eTrans)
where eTrans 0 'e' = [1]
This would work exactly the same (ie it would accept the correct
language), but would have one extra state in any ndfa that had epsilon.
Does that make it incorrect?

Post by alex cheng
Ok, here is my interpretation of what an ndfa should look like, if
given a regex. Feel free to agree or disagree.
EmptySet = ([0], 0, [], no transitions)
Epsilon = ([0], 0, [0], no transitions)
Symb '0' = ([0,1], 0, [1], only transition is from 0 to 1 on receipt of '0')
Let me know what you think.
-chris

[David Zhao]

It is in your very best interests to minimize the number of states that you use
for the machine of each regular expression. Just think... when you call
ndfaToDfa, for each state that you save, the number of states in the DFA is
reduced by a factor of 2.

David

Post by Danny Hoodin
Couldn't Epsilon be
([0,1],1,[1],eTrans)
where eTrans 0 'e' = [1]
This would work exactly the same (ie it would accept the correct language),
but would have one extra state in any ndfa that had epsilon. Does that make
it incorrect?