Re: NFA and negation/conjunction

> 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

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