Re: Rehash of regular expression question... (David O'Brien)
Mon, 21 Feb 1994 00:19:20 GMT

          From comp.compilers

Related articles
Regular Expression Question... dschieb@muse.CV.NRAO.EDU (1993-12-14)
Rehash of regular expression question... (1994-02-18)
Re: Rehash of regular expression question... (1994-02-21)
Re: Rehash of regular expression question... jhummel@cy4.ICS.UCI.EDU (Joe Hummel) (1994-02-24)
| List of all articles for this month |

Newsgroups: comp.compilers
From: (David O'Brien)
Keywords: DFA, theory
Organization: George Washington University
References: 93-12-062 94-02-125
Date: Mon, 21 Feb 1994 00:19:20 GMT

: A while back Darrell Schiebel asked (using a slightly different notation):

: How to prove that ( (1 + a) b* ) = (a + b)*

I assume that the above is suppose to be ((1+a)b*)*

: in regular expression notation, where 1 denotes the empty string.

: Algebraically, one could proceed as follows:

: ( (1 + a) b* )* = (b* + a b*)* distributivity
: = b** (a b* b**)* (X + Y)* = X* (Y X*)*
: = b* (a b* b*)* X** = X*
: = b* (a b*)* X* X* = X*

Isn't the case above X* Y* ? Not X* X*. If so then you
can't do this. If the above is correct, please explain

: Interestingly, the general problem of proving a regular expression
: involving symbols x1, x2, ..., xn equal to (x1 + x2 + ... + xn)* is
: not just NP-hard, but P-space complete (note: P-time <= NP-time <= P-space,
: with equality if P = NP).

Hum, from Alg class I don't agree that determining if two reg langs
are equal is NP-hard. I believe we can take any regular expression
and convert it to a NFA in P-time. We can take two NFA's and take
their Unions, Compliments and Intersections in P-time. Then we can
create new NFA that is (L1 intersect L2') union (L1' intersect L2).
If L1 = L2 then L3 is empty. We can determine in P-time a NFA/DFA
is empty. Therefore, isn't the above problem P, and not NP?

-- David O'Brien (

Post a followup to this message

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