# Re: How to compute a regex which is the difference between two regexes?

## Gene <gene.ressler@gmail.com>

Sun, 3 Jan 2010 16:52:14 -0800 (PST)

*From comp.compilers*

| List of all articles for this month |

**From: ** | Gene <gene.ressler@gmail.com> |

**Newsgroups: ** | comp.compilers |

**Date: ** | Sun, 3 Jan 2010 16:52:14 -0800 (PST) |

**Organization: ** | Compilers Central |

**References: ** | 10-01-013 |

**Keywords: ** | lex, comment |

**Posted-Date: ** | 04 Jan 2010 11:20:59 EST |

On Jan 3, 11:20 am, Peng Yu <pengyu...@gmail.com> wrote:

*> Suppose that I have two regular sets A and B that are generated by two*

*> regular expressions. I'm wondering if there is always a regular*

*> expression that can generated the difference between the two sets,*

*> i.e., A-B. If there is such regular expression, is there a mechanical*

*> way to generated such regular expression.*

Sure. RL's are closed under complement (flip the accepting and non-

accepting states of the corresponding DFA) and intersection (build the

cross product DFA and make a state a x b accepting iff both a and b

are accepting in the original machines). Now you know how to build

the DFA for intersection(A, not(B)), which is the same as A-B. To go

back and forth from DFA to regex, use the constructions in any proof

of Kleene's theorem. John may be remembering that the difference of

CFLs is not necessarily context free.

[You're right. "Never mind." -John]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.