Sat, 15 May 2010 14:32:00 -0400

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: | Stefan Monnier <monnier@iro.umontreal.ca> |

Newsgroups: | comp.compilers |

Date: | Sat, 15 May 2010 14:32:00 -0400 |

Organization: | Compilers Central |

References: | 10-05-078 10-05-081 |

Keywords: | lex, DFA |

Posted-Date: | 16 May 2010 01:49:53 EDT |

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

That seems to describe the rules for the concatenation of R1 and R2, but

not their conjunction, right (where the conjunction R1&R2 is a regexp

that describes the set of strings corresponding to the intersection of

the set of strings described by R1 and by R2).

Stefan

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.