Sun, 16 May 2010 14:05:08 +0330

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: | klyjikoo <klyjikoo@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Sun, 16 May 2010 14:05:08 +0330 |

Organization: | Compilers Central |

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

Keywords: | lex, DFA |

Posted-Date: | 16 May 2010 11:36:40 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.