Re: RegEx: AND operator

ahelin@student.oulu.fi (Aki Helin)
13 Oct 2003 15:26:14 -0400

          From comp.compilers
Related articles
RegEx: AND operator nikt@wp.pl (jan) (2003-10-12)
Re: RegEx: AND operator vannoord@let.rug.nl (2003-10-13)
Re: RegEx: AND operator ahelin@student.oulu.fi (2003-10-13)
Re: RegEx: AND operator henry@spsystems.net (2003-10-14)
Re: RegEx: AND operator clint@0lsen.net (Clint Olsen) (2003-10-14)
Re: RegEx: AND operator nikt@wp.pl (jan) (2003-10-18)
Re: RegEx: AND operator nikt@wp.pl (jan) (2003-10-19)
| List of all articles for this month |
From: ahelin@student.oulu.fi (Aki Helin)
Newsgroups: comp.compilers
Date: 13 Oct 2003 15:26:14 -0400
Organization: Oulun Puhelin Oyj - Baana
References: 03-10-045
Keywords: lex
Posted-Date: 13 Oct 2003 15:26:14 EDT

jan <nikt@wp.pl> wrote:


> The algorithms for translation of regex into NFA are popular; however,
> in none have I seen support for the AND (&) operator.


This is usually called the intersection. Regular languages are closed
under this (and just about any other) operation, so there must be a
NFA for each A & B.


> implemented as another NFA that is run in the required range
> (eg. regex (a.* & ~abc)+ would make one NFA (a.*)+ and for each
> matched (a.*) it would test the other NFA: ~abc) but that's not a good
> solution, besides it won't allow creating NFA. Anybody can help?


If A and B are regular expressions, you could for example compile both
of them to DFAs. Then by making a new DFA where each state is a cartesian
product of the states of DFAs of A and B, you can easily make an automata
that will accept a string if and only if both A and B accept it.


--
aki helin

Post a followup to this message

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