Mon, 21 Feb 1994 00:19:20 GMT

Related articles |
---|

Regular Expression Question... dschieb@muse.CV.NRAO.EDU (1993-12-14) |

Rehash of regular expression question... mark@freenet.uwm.edu (1994-02-18) |

Re: Rehash of regular expression question... dobrien@seas.gwu.edu (1994-02-21) |

Re: Rehash of regular expression question... jhummel@cy4.ICS.UCI.EDU (Joe Hummel) (1994-02-24) |

Newsgroups: | comp.compilers |

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

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)

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.