Re: NFA and negation/conjunction

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 .

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