Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!emory!wa4mei!holos0!lbr
From: lbr@holos0.uucp (Len Reed)
Newsgroups: comp.lang.perl
Subject: Re: regular expressions
Message-ID: <1991Jun7.141151.625@holos0.uucp>
Date: 7 Jun 91 14:11:51 GMT
References: <1991Jun4.175023.6509@serval.net.wsu.edu>
Organization: Holos Software, Inc., Atlanta, GA
Lines: 52

In article <1991Jun4.175023.6509@serval.net.wsu.edu> hakimian@tek4.eecs.wsu.edu (Karl Hakimian - staff) writes:
>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.

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

It's not meaningful to talk of the regular expressions supported by Unix
since different Unix tools support different concepts of regular expressions.
Grep does not support a full set of regular expressions; perl and egrep do.

A regular is defined recursively as follows:

1) A single character from a given set.
	or
2) Concatenation of two regular expressions.
	or
3) Kleene closure of a regular expression.  (The * operator, usually written
   in superscript in textbook descriptions.)

	or
4) Disjunction of two regular expressions.  (The | operator.)

Syntactically there must be a method of grouping, of course, to show
the difference between a(bc)* and abc*.

Since perl supports all of these, it is complete.  Grep, ex, ed, and
several others lack the disjunction operator.

Just because you *can* do something doesn't make it easy, natural, or
efficient, though.  A bare-bones implementation of regular expressions
will accept more languages than grep, but grep allows nice syntactic
shortcuts like [a-z] and [^xyz].  Perl has these in spades.  You sure
don't want to have to say a|b|c|d|e|f ....

Since perl's expressions *are* complete, you *can* express your problem
if it's regular.  Your problem didn't seem regular to me off hand, since it
can't be easily expressed as a regular expression.  But it makes for
a simple finite automaton (my DFA solution had 9 states), so it is regular.

In perl, you want
   /foo/ && !/bar/

Coercing this into one regular expression, while provably do-able, is
ill advised.  I lost interest real quick in hand converting my
DFA to a regular expression.
-- 
Len Reed
Holos Software, Inc.
Voice: (404) 496-1358
UUCP: ...!gatech!holos0!lbr