Re: NFA and negation/conjunction

Although the same method for complementation of DFA can not be applied
in the case of NFA, but I think the correct implementation can be
achieved in some way tricky. Applying the usual interchanging of final
states in the case of NFA would not work when there are some
acceptable string that is prefix of another acceptable string by NFA.
Usually after checking an input string against an NFA these three
situations can occur:


1) The NFA accepts the string
2) The NFA halts when checking string
3) Both situation 1 and 2 occurred


Comparing these situation it would be possible to simulate NFA
complementation by surrounding NFA with a complementation module that
works as follows: in the situation 1 and 3 of above, module simply
rejects the input string and in situation 2 the module accepts the
string.


The final note that using this implementation it is also possible
to work about intersection of NFA's with applying the deMorgan rule;
however it would need epsilon transitions.

Return to the comp.compilers page.
Search the comp.compilers archives again.