which one is correct ?

Question

Consider R1 and R2 are two regular expression then equality of two regular expression compute in

A) polynomial time  B) Exponential time

C) logarithmic Polynomial time  D) Constant Time

Answer 1

• Convert to NFA
• Convert to DFA
• Minimize DFA - minimal DFA is unique

So, must be exponential as there is no other way to do this AFAIK. 

Comments

For equivalence of DFA , we need to find cross product of both DFA's, and finals should come together.

But we can find the crossproduct by NFA's itself.

---

How's that done? I'm not getting even for DFA..

---

Exponential time becouse check two reguler expression equal is nothing but check two FA equalencnce.

Answer 2

The problem of deciding whether two regular expressions are equivalent is PSPACE-complete .as PSPACE is in EXP TIME.ans is EXP TIME

Comments

@Varun ,what is BPP ?

---

i dont know about BPP.

Answer 3

I think its D) Constant  time   .

Comments

please explain

---

Regular language can be finite or infinite . If infinite then there must be a pattern on it . To check it we need O(1) time . But in case of its finite then we need not to check . cause every finite set is regular .

this is my understanding, correct me if anything wrong :D.

---

u r correct my thinking matches ur thining :)

---

This is not exam time- if confused you can try google than going with intuition. This requires exponential time.

Answer 4

it should be polynomial time

Comments

how can u say polnomial time for that .

Answer 5

www.win.tue.nl/mdseminar/pres/ploeger-19-10-06.pdf
Polynomial Time.
 

Answer 6

Exponential time.