Re: Rehash of regular expression question...

: 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
how.


: 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 (dobrien@seas.gwu.edu)
--

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