Fri, 14 May 2010 22:59:02 +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) |

[2 later articles] |

From: | klyjikoo <klyjikoo@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Fri, 14 May 2010 22:59:02 +0330 |

Organization: | Compilers Central |

References: | 10-05-078 |

Keywords: | lex |

Posted-Date: | 15 May 2010 02:10:40 EDT |

Recently I Built a tool for generating NFA's from simple regexes and

then reducing the NFA,i simply used the following rule for conjunction

of NFA's during construction:

If N1 and N2 are the NFAs associated with regular expression R1 and

R2 respectively, then we construct the N' associated with R1R2 as

follows:

a) For each final state s of N1, we make any transition that initiate

from start state of N2 also to initiate from s.

b) Start state of N1 would be start state of N'.

c) Final states of N2 would be final states of N'.

d) If start state of N2 is a final state then final states of N1 also

would be final states of N'.

e) We eliminate start state of N2 and all related transition if it is

a useless state in N'.

For negation of NFA you could interchange the start state and final

states of Original NFA .

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.