Path: utzoo!dciem!array!colin
From: colin@array.UUCP (Colin Plumb)
Newsgroups: comp.lang.perl
Subject: Re: regular expressions
Message-ID: <1910@array.UUCP>
Date: 11 Jun 91 00:43:08 GMT
References: <1991Jun4.175023.6509@serval.net.wsu.edu> <1991Jun8.145419.22522@NCoast.ORG>
Organization: Array Systems Computing, Inc., Toronto, Ontario, CANADA
Lines: 27

In article <1991Jun8.145419.22522@NCoast.ORG> allbery@ncoast.ORG (Brandon S. Allbery KF8NH) writes:
>Regexps are most capable in combination with other constructs; so, while you
>can't write a regexp that matches /foo/ iff it does not also match /bar/, you
>*can* say (in Perl):  (($str !~ /bar/) && ($str =~ /foo/)).  (I could argue
>that Perl is nothing more than an extended regexp parser, if I were feeling
>whimsical....)

Sorry, Brandon, you need to re-read your formal languages textbook.
The set of formal languages is closed under complemenbt and
intersection as well as union (the | operator), kleene closure (the *
operator) and concatenation (the null operator).  The difference
between two regular languages is itself a regular language.  In other
words, given any two, arbitrarily complex regular expressions A and B,
there is a regular expression C that matches iff A matches and B does
not.

I've played with finite automaton tools that implement the difference
operator.

It just so happens that deterministic finite automata, nondeterministic
FA's, regular expressions involving difference, intersection, etc., and
regular expressions using only "", | and * are equivalent in power
(there are algorithms for translating among them), so there's no
theoretical need to provide more than one means of expressing what you
want.  It's sure convenient, though.
-- 	
	-Colin