Wed, 19 May 2010 11:40:56 +0330

Related articles |
---|

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

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

Re: NFA and negation/conjunction sh006d3592@blueyonder.co.uk (Stephen Horne) (2010-05-15) |

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: | klyjikoo <klyjikoo@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Wed, 19 May 2010 11:40:56 +0330 |

Organization: | Compilers Central |

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

Keywords: | lex |

Posted-Date: | 19 May 2010 22:23:55 EDT |

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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.