Re: NFA and negation/conjunction

> That seems to describe the rules for the concatenation of R1 and R2, but
> not their conjunction,


Sorry for false responce,


I think For both intersection and complement of DFA's, there are
standard algorithms that can be found in textbooks, also for
elimination of useless states and minimization of DFA .


In case of NFA also applying the same algorithms is possible, except
that minimization of NFA is PSPACE-Complete.


specially for Negation of NFA, i could simple interchange the start
state and final states of original NFA, that this lead to several
start states and only one final state and a number of dead state. For
avoidance of several start state, i can follow this rules:
a) Adding a new state s ,we make any transition that initiate
        from current start states also to initiate from s.
b) State s in above would be new start state.
c) Elimination of any non-reachable state in new NFA.


For intersection of NFA's i can use the standard algorithms that
produce an NFA with |n*m| states in the case of two input NFA with |n|
and |m| states. But a solution resulting less states would be
applying the deMorgon's Law. I could first negate each automata,
compute the union of them, then again negate the final result.


Then I have used the following rule for computing union of NFA's :


If N1 is the NFA associated with regular expression R1 and N2 is the
NFA associated with regular expression R2 ,then we construct the N'
associated with R1|R2 as follows:


a) We add a new state s and mark it as start state of N', then we make
any transition that initiate from start states of N1 and N2 also to
initiate from s.
b) Final states of N1 and N2 would be final states of N'.
c) If any of start state of N1 and N2 is a final state then start
state of N' also would be a final state.
d) We eliminate start state of N1 and N2 and all related transition if
they are useless states in N'.

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