8 Jun 2005 22:34:36 -0400

Related articles |
---|

regular expression question gvheurn@gmail.com (Gijs) (2005-06-08) |

Re: regular expression question gah@ugcs.caltech.edu (glen herrmannsfeldt) (2005-06-08) |

Re: regular expression question 148f3wg02@sneakemail.com (Karsten Nyblad) (2005-06-08) |

Re: regular expression question daw@taverner.cs.berkeley.edu (2005-06-08) |

Re: regular expression question gvheurn@gmail.com (Gijs) (2005-06-09) |

Re: regular expression question nicola.musatti@gmail.com (Nicola Musatti) (2005-06-09) |

Re: regular expression question cfc@shell01.TheWorld.com (Chris F Clark) (2005-06-09) |

Re: regular expression question snicol@apk.net (Scott Nicol) (2005-06-10) |

Re: regular expression question snicol@apk.net (Scott Nicol) (2005-06-10) |

[4 later articles] |

From: | Karsten Nyblad <148f3wg02@sneakemail.com> |

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.