Re: regular expression question

Karsten Nyblad <>
8 Jun 2005 22:34:36 -0400

          From comp.compilers

Related articles
regular expression question (Gijs) (2005-06-08)
Re: regular expression question (glen herrmannsfeldt) (2005-06-08)
Re: regular expression question (Karsten Nyblad) (2005-06-08)
Re: regular expression question (2005-06-08)
Re: regular expression question (Gijs) (2005-06-09)
Re: regular expression question (Nicola Musatti) (2005-06-09)
Re: regular expression question (Chris F Clark) (2005-06-09)
Re: regular expression question (Scott Nicol) (2005-06-10)
Re: regular expression question (Scott Nicol) (2005-06-10)
[4 later articles]
| List of all articles for this month |

From: Karsten Nyblad <>
Newsgroups: comp.compilers
Date: 8 Jun 2005 22:34:36 -0400
Organization: Compilers Central
References: 05-06-045
Keywords: lex, DFA
Posted-Date: 08 Jun 2005 22:34:36 EDT

Gijs wrote:
> Don't know if this is the right group for this. 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.
> So for example I want to have a RE that matches all strings except for
> the string "hello". How do you do this?
> I have the feeling this is a very dumb question, but I have no idea how
> to get this.
> Thanks in advance!
> Gijs
> [It's not a dumb question, it's a hard question. The complement of a RE
> is usually not a RE. My practical advice would be to look for "hello" and
> reverse the sense of the test in the surrounding code. -John]

Sorry John, but you are wrong. I guess you both know that any DFA can
be expressed as an RE and vice versa. That is proved in any book on
formal languages.

Let R be an RE for which we want the complement. Let A be the alphabet
of R. Let D be the minimal DFA expressing R. Add a new non accepting
state S to D giving D'. Add new transitions to D' such that if a state
S' has no transsion on a letter L of A, then a transsion from S' to S is
added on L. Please note that using this rule all states have a
transition on all letters of A, and in particullar all transitions from S
loops back to S. Call the new DFA D". In D" change all accepting
states to non accepting states and vice versa. This last DFA accepts
the complement and can be converted into an RE.

I do not know of any simple way of constructing an RE that accepts the
complement of an other RE.

Karsten Nybla
d148f3wg02 at sneakemail dot com
[Oh, right, darn those senior moments when your last CS theory class
was 25 years ago. Can you put any limits on the size of the resulting
RE, or might it be like LR(k) to LR(1), too ugly to use? -John]

Post a followup to this message

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