On 24/05/2013 07:44 PM, Kevin Wampler 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.

Does the situation change if we disallow the Kleene star?

Post a reply to this message