Re: NFA and negation/conjunction

klyjikoo <klyjikoo@gmail.com>
Fri, 14 May 2010 22:59:02 +0330

          From comp.compilers

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)
[2 later articles]
| List of all articles for this month |

From: klyjikoo <klyjikoo@gmail.com>
Newsgroups: comp.compilers
Date: Fri, 14 May 2010 22:59:02 +0330
Organization: Compilers Central
References: 10-05-078
Keywords: lex
Posted-Date: 15 May 2010 02:10:40 EDT

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 .



Post a followup to this message

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