Re: regular expression question

"Gijs" <gvheurn@gmail.com> writes:


> Can anyone tell me how
> to create a regular expression that matches all except for one string?
> I tried to use the complement sign ^, but this is only usable for one
> character, not for a whole string.


Other people have suggested converting to a DFA and complementing
this, which works for all regular languages. But for the complement
of a single string, it isn't that hard to make a regular expression:


  1) For the empty string, the complement is .+, where "." matches any
        character in the alphabet.


  2) For a non-empty string starting with the character a and
        continuing with the suffix s (i.e., the string is equal to as,
        where a is a single character and s is a (possibly empty) string),
        the complement is ("" | [^a] .* | a s'), where s' is the
        complement of s. I.e., either the empty string, any string not
        starting with a or a string starting with a followed by the
        complement of s.


                Torben

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