edited by
1,343 views

2 Answers

5 votes
5 votes
Look we can compare regular expressions by constructing their DFA

If L(M1)=L(M2)

Now for each N input Regular Expression there will be At most 2^n States in it's DFA(may be less, but this is the upper bound)

so simply the complexity will be O(2^n)

correct me,if needed :D
0 votes
0 votes
A) Constant time

Equality of two regular expression is decidable. Decidable means 'yes' and 'no' answer is possible in finite amount of time. Because it will not causing any loop. So, equality of two regular expression can be measured in constant time.

Related questions

1 votes
1 votes
2 answers
1
shekhar chauhan asked Jun 8, 2016
1,754 views
If r1 and r2 are 2 Regular Expression Such thatr1 = (a+b)* r2 = (a*+b*+a*b*+b*a*)What are the different case's in which r1 = r2 ?Please Explain with an example
3 votes
3 votes
2 answers
3
Sunil8860 asked Sep 4, 2017
786 views
1 votes
1 votes
1 answer
4
gate_forum asked May 29, 2016
2,228 views
prove the identity: (a*ab + ba)* a* = (a + ab + ba)*