Thu, 20 May 2010 11:34:05 +0200

Related articles |
---|

[3 earlier articles] |

Re: NFA and negation/conjunction monnier@iro.umontreal.ca (Stefan Monnier) (2010-05-15) |

Re: NFA and negation/conjunction klyjikoo@gmail.com (klyjikoo) (2010-05-16) |

Re: NFA and negation/conjunction cfc@shell01.TheWorld.com (Chris F Clark) (2010-05-16) |

Re: NFA and negation/conjunction torbenm@diku.dk (2010-05-17) |

Re: NFA and negation/conjunction klyjikoo@gmail.com (klyjikoo) (2010-05-19) |

Re: NFA and negation/conjunction rsc@swtch.com (Russ Cox) (2010-05-19) |

Re: NFA and negation/conjunction torbenm@diku.dk (2010-05-20) |

From: | torbenm@diku.dk (Torben Ęgidius Mogensen) |

Newsgroups: | comp.compilers |

Date: | Thu, 20 May 2010 11:34:05 +0200 |

Organization: | UNI-C |

References: | 10-05-078 10-05-100 10-05-111 |

Keywords: | lex |

Posted-Date: | 20 May 2010 15:24:29 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.