Re: NFA and negation/conjunction

klyjikoo <klyjikoo@gmail.com> writes:


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


When working with NFAs, there is the "small" issue that one doesn't
generally put arrows to a failure state for transitions, one just
omits them and the machine halts without accepting. Epsilon
transitions are another aspect of NFAs that distinguish it from DFAs.
Resolving these issues generally gets one back to a DFA and one has to
face the state explosion issue.


So, while NFAs and DFAs have the same expressive power, they don't do
so with the exact same complexity level. Some things are easier with
NFAs, others with DFAs, and there aren't simple linear algorithms to
convert the two formulations. That holds true with both of those
compared to regular expressions also. If that wasn't true, my current
job would be a lot easier (and I'd have to do something else).


Hope this helps,
-Chris


******************************************************************************
Chris Clark email: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. Web Site: http://world.std.com/~compres
23 Bailey Rd voice: (508) 435-5016
Berlin, MA 01503 USA twitter: @intel_chris
------------------------------------------------------------------------------

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