Register

Regular Expression time complexity

• edited by
1,396 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
User Avatar
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.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
2 answers
1
shekhar chauhan asked Jun 8, 2016
1,827 views
Automata Regular expression
If r1 and r2 are 2 Regular Expression Such that r1 = (a+b)* r2 = (a*+b*+a*b*+b*a*) What are the different case's in which r1 = r2 ? Please Explain with an example
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
User Avatar
3 votes
3 votes
2 answers
3
Sunil8860 asked Sep 4, 2017
817 views
regular expression
User Avatar
1 votes
1 votes
1 answer
4
gate_forum asked May 29, 2016
2,260 views
regular expression algebra
prove the identity: (a*ab + ba)* a* = (a + ab + ba)*
prove the identity: (a*ab + ba)* a* = (a + ab + ba)*
User Avatar
Link Copied!