Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!aplcen!boingo.med.jhu.edu!haven.umd.edu!uvaarpa!mmdf
From: worley@compass.com (Dale Worley)
Newsgroups: comp.lang.perl
Subject: regular expressions
Message-ID: <1991Jun6.202601.16963@uvaarpa.Virginia.EDU>
Date: 6 Jun 91 20:26:01 GMT
Sender: mmdf@uvaarpa.Virginia.EDU (Uvaarpa Mail System)
Reply-To: worley@compass.com
Organization: The Internet
Lines: 33


   From: hakimian@tek4.eecs.wsu.edu (Karl Hakimian - staff)

   I would like to talk with and and all regular expression gurus. It seems that
   the regular expressions that are supported by perl (and unix) do not accept
   any and all regular languages. If this is not true, I would love to learn how
   to do some of the things that I am trying to do.

Perl's regular expressions *do* accept all regular languages.  It
contains single characters, concatenation, *, and |, which is enough.
The problem you're having is that there is no explicit "doesn't
contain" operator in Perl.  However, that's not needed -- you can
always rephrase "doesn't contain" in terms of the other operators.
The transformation is messy, though.  See any book that discusses
regular languages and DFAs.

   For example, how would you write a regular expression that accepts a string
   with "foo" iff "bar" is not also in the string.

(I assume that you mean "accepts the strings that contain 'foo' and do
not contain 'bar'".)

Personally, I'd construct the DFAs that accept "^.*foo.*$" and
"^.*bar.*$".  Then I'd combine them using the standard "A intersect
(complement B)" construction to get a DFA that accepted strings
containing foo but not bar.  Then I'd do the horrible transformation
to turn that DFA into a regular expression.

But there's probably a better way.

Dale Worley		Compass, Inc.			worley@compass.com
--
Take nothing by force that you don't want.