Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!wuarchive!uunet!convex!convex!connolly
From: connolly@convex.convex.COM (Dan Connolly)
Newsgroups: comp.lang.perl
Subject: Re: regular expressions
Message-ID: <1991Jun06.000718.19691@convex.com>
Date: 6 Jun 91 00:07:18 GMT
References: <1991Jun4.175023.6509@serval.net.wsu.edu> <1991Jun5.183443.11524@intellistor.com>
Sender: connolly@convex (Dan Connolly)
Organization: CONVEX Computer Corporation
Lines: 25
Nntp-Posting-Host: pixel.convex.com

In article <1991Jun5.183443.11524@intellistor.com>, wicklund@intellistor.com (Tom Wicklund) writes:
|> In <1991Jun4.175023.6509@serval.net.wsu.edu> hakimian@tek4.eecs.wsu.edu (Karl Hakimian - staff) writes:
|> 
|> >For example, how would you write a regular expression that accepts a string
|> >with "foo" iff "bar" is not also in the string.
|> 
|> 

What definition of "regular language" are you [Karl Hakimian] working from?

The definition of regular language I've seen is:
For an alphabet A, the regular languages over A are
the empty language, empty-string language, the single-character-string languages, and all finite applications of union, concatenation, and kleene-star
of other regualar languages.

In unix-speak, the alphabet is the 127 ascii characters (1-128).
The empty language is tough to come up with. What's a regexp that matches nothing?
The empty-string language is /^$/.
The single-character-string languages are /a/, /b/, /c/, /\\/, etc.
The union of two languages A and B is /A|B/.
The concatenation of two languages A and B is /AB/.
The kleene star of A is /A*/.
Aside from some details about ()'s, that would seem to me to fit the bill.

Dan