search

michaelinux / mini-java

Automatically exported from code.google.com/p/mini-java
0 stars 0 forks source link

Implement NFA #12

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
NFA is similar to DFA except they can accept so called "epsilon"
transitions, transitions without input. Sometimes, DFA is hard to build
directly; however, by using NFA as a bridge between formal language and the
corresponding DFA, we break the whole process into two steps: first, build
the NFA, which is easy; then, convert the NFA to an equivalent DFA.

NOTE: NFA is not supposed to be run by a simulator like DFA; this is why we
don't introduce the relationship between NFA and DFA, although they are
quite similar.

Original issue reported on code.google.com by lemontree.cool on 4 Sep 2008 at 3:13

GoogleCodeExporter commented 9 years ago 
NFA cannot be converted to DFA by "merging" the source and target states of it's
epsilon transitions. Since transition has a direction, epsilon transition 
doesn't
necessary mean an equivalent relationship between the source and target state.

Original comment by lemontree.cool on 5 Sep 2008 at 3:01

GoogleCodeExporter commented 9 years ago

Original comment by lemontree.cool on 11 Sep 2008 at 3:14