2 votes 2 votes 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 Theory of Computation regular-expression + – Ankit Chourasiya asked Sep 13, 2015 Ankit Chourasiya 1.3k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 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. gatecse answered Sep 15, 2015 gatecse comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Praveen Saini commented Sep 16, 2015 reply Follow Share 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. 1 votes 1 votes gatecse commented Sep 16, 2015 reply Follow Share How's that done? I'm not getting even for DFA.. 0 votes 0 votes Mohit Kumar 6 commented Mar 16, 2018 reply Follow Share Exponential time becouse check two reguler expression equal is nothing but check two FA equalencnce. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes The problem of deciding whether two regular expressions are equivalent is PSPACE-complete .as PSPACE is in EXP TIME.ans is EXP TIME varunraj answered Mar 16, 2018 varunraj comment Share Follow See all 2 Comments See all 2 2 Comments reply ankitgupta.1729 commented Mar 16, 2018 reply Follow Share @Varun ,what is BPP ? 1 votes 1 votes varunraj commented Mar 16, 2018 reply Follow Share i dont know about BPP. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes I think its D) Constant time . Pranay Datta 1 answered Sep 13, 2015 Pranay Datta 1 comment Share Follow See all 4 Comments See all 4 4 Comments reply goku commented Sep 14, 2015 reply Follow Share please explain 0 votes 0 votes Pranay Datta 1 commented Sep 15, 2015 reply Follow Share 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. 0 votes 0 votes focus _GATE commented Oct 4, 2015 reply Follow Share u r correct my thinking matches ur thining :) –1 votes –1 votes Arjun commented Oct 4, 2015 reply Follow Share This is not exam time- if confused you can try google than going with intuition. This requires exponential time. 2 votes 2 votes Please log in or register to add a comment.
0 votes 0 votes it should be polynomial time Saurav answered Sep 13, 2015 Saurav comment Share Follow See 1 comment See all 1 1 comment reply Tendua commented Sep 14, 2015 reply Follow Share how can u say polnomial time for that . 0 votes 0 votes Please log in or register to add a comment.