Re: NFA and negation/conjunction

klyjikoo <klyjikoo@gmail.com> writes:


> 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.


> 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.


You can do that, but the result won't be an NFA. So you get into
trouble when you want to build on top of this, such as (not A) | B or
(not A)*.


The main problem with complementing an NFA is that the semantics of an
NFA is that if there exist a path from initial to final state spelling
out the input, then you accept. Complementing this means that there
does not exist any such path. This change of quantifier means that you
need an automaton that requires all paths that spell out the input to
reach a final state. In a DFA, this is the same (there is only one
path), but in an NFA, it is quite different.


You could use alternating aotomata: These have two kinds of states: OR
states and AND states. In an OR state, you just need one of the
transitions leading out of the state to reach a final state (as in an
NFA), but in an AND state, you need all the transitins out of the state
to lead to a final state.


> 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.


This basically shows that complementation is a harder problem than
intersection: With complement, you can get intersection, but you can't
get complement from intersection.


BTW, instead of looking at complement, you could look at set difference.
This has the advantage that you don't need to specify the alphabet
(which you do for complement). Obviously, (with some abuse of LaTeX
notation):


\complement A = \Sigma* \setminus A


A \setminus B = A \intersect (\complement B)
                            = \complement (\complement A \union B)


so once you have one, you have the other. But set difference can be
easier to work with, e.g., if you use derivatives.


Torben

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