On 5/24/2013 12:22 PM, Warp wrote:
> Kevin Wampler <nob### [at] nowherenet> wrote:
>> On 5/24/2013 11:20 AM, Orchid Win7 v1 wrote:
>>> Suppose I give you two arbitrary regular expressions. Are they equivalent?
>
>> It depends on what you specifically mean by "regular expression", but
>> probably this problem is PSPACE-complete.  From what I can tell is
>> generally solved by converting each regexp into a DFA and checking if
>> they are isomorphic.
>
> No. Two regular expressions expressing the same "language" (ie. matching
> the exact same things) is not a question of isomorphism. Isomorphism is
> a much stricter comparison.

I should have been more explicit: solved by converting each regex into a 
*minimal* DFA  and checking if they are isomorphic.

Graph isomorphism is of course GI-complete, but the conversion to a 
minimal DFA is in general PSPACE-complete.

Post a reply to this message