Regular Expression time complexity

Question

The equality of two regular expression is computed in? Give reasons also..

• A. Constant Time
• B. polynomial time
• C. logarithmic Polynomial time
• D. Exponential time

Answer 1

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

Comments

Exponential time

Answer 2

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.

Comments

@srestha

What is your approach for equivalency?

I know it is decidable but,

I mean what are the steps taken which ensure the equivalency between the regular expressions. How to prove that?

---

See what I think @Kapil

regular language is finite.

So, we can say if it has same regular expression with another regular language.

here 'yes' and 'no' ans is possible. rt?

---

yes,.. but google says exponential time.

www.dcc.fc.up.pt/dcc/Pubs/TReports/TR07/dcc-2007-07.pdf

1.  
2.  

---

Given two re r1 and r2 .

Construct DFA for both .

Then check whether L(M1)=L(M2).rt ?

---

yes, it is a classic method. 

design NFA then convert to DFA by subset construction method which takes around ∑* 2ⁿ time .

---

but how exponential time?

---

Constructing the DFA for a regular expression of size n has the time and memory cost of O($2^{n}$)

---

yes.. but we can apply lazy evaluation method for that... it can reduce this cost...

but instead worst case is O(2ⁿ)

---

Exponential time

---

regular expressions are not finite they can produce infinite length string also eg  a*