Re: regular expression question

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]

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