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
Related articles
How to compute a regex which is the difference between two regexes? pengyu.ut@gmail.com (Peng Yu) (2010-01-03)
Re: How to compute a regex which is the difference between two regexes mhelvens@gmail.com (Michiel) (2010-01-03)
Re: How to compute a regex which is the difference between two regexes egagnon@j-meg.com (Etienne M. Gagnon) (2010-01-03)
Re: How to compute a regex which is the difference between two regexes gene.ressler@gmail.com (Gene) (2010-01-03)
Re: How to compute a regex which is the difference between two regexes mciura@gmail.com (Marcin Ciura) (2010-01-04)
Re: How to compute a regex which is the difference between two regexes max@gustavus.edu (Max Hailperin) (2010-01-04)
Re: How to compute a regex which is the difference between two regexes kkylheku@gmail.com (Kaz Kylheku) (2010-01-05)
Re: How to compute a regex which is the difference between two regexes kkylheku@gmail.com (Kaz Kylheku) (2010-01-06)
Re: How to compute a regex which is the difference between two regexes cfc@shell01.TheWorld.com (Chris F Clark) (2010-01-11)
| 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.