30 votes 30 votes Which two of the following four regular expressions are equivalent? ($\varepsilon$ is the empty string). $(00)^ * (\varepsilon +0)$ $(00)^*$ $0^*$ $0(00)^*$ (i) and (ii) (ii) and (iii) (i) and (iii) (iii) and (iv) Theory of Computation gate1996 theory-of-computation regular-expression easy + – Kathleen asked Oct 9, 2014 edited Mar 3, 2018 by kenzou Kathleen 10.1k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply One commented Aug 15, 2016 reply Follow Share 1.) 0^n where n>=0 2.) 0^2n where n>=0 3.) 0^n where n>=0 4.) 0^2n+1 where n>=0 2 votes 2 votes rajan commented Oct 7, 2016 i edited by rajan Dec 3, 2016 reply Follow Share basic explanation by taking (00)∗(ε+0) .in it (00)* gives even no of 0's then if i do (00)*epsilon which given also even no of zeros and for (00)*0 gives odd no so totally we can say they given all possible odd and even no's of zeros and (iii) 0* also gives so c will be answer 6 votes 6 votes air1ankit commented Dec 11, 2017 reply Follow Share (00)∗(ε+0)(00)∗(ε+0) (00)∗(00)∗ 0∗0∗ 0(00)∗ please expend all the above options 0 votes 0 votes Divyanshum29 commented Jun 24, 2018 reply Follow Share 1- is just 00*(ε+0) 2- is (00)* 3- is 0* 4- is 0(00)* 1 votes 1 votes Please log in or register to add a comment.
Best answer 31 votes 31 votes Answer is C. You can have any no. of $0$'s as well as null. A is false because you cannot have single $0$ in ii). same for option B. In D you are forced to have single $0$ in iv) whereas not in iii). Gate Keeda answered Oct 10, 2014 edited Jun 15, 2018 by Milicevic3306 Gate Keeda comment Share Follow See 1 comment See all 1 1 comment reply raja11sep commented Jul 14, 2021 reply Follow Share ii + iv = iii = i. ii => all even length. iv => all odd length. Note: Epsilon is an even length string whose length is 0. 0 votes 0 votes Please log in or register to add a comment.
7 votes 7 votes option c is right. abhishekmehta4u answered Mar 28, 2019 abhishekmehta4u comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes i)(00)*(0+ε) it generates any number of 0's ii) (00)* it generates the only even number of 0's iii)0* it generates any number of 0's iv)0(00)* it generates the only odd number of zeroes. So correct option is c i.e. i) and iii) Parth Shah answered Feb 23, 2018 Parth Shah comment Share Follow See all 2 Comments See all 2 2 Comments reply shubham02 commented Aug 17, 2018 reply Follow Share but as R + epsilon is = R so opion A will become (00)* ...???? 0 votes 0 votes Parth Shah commented Aug 17, 2018 reply Follow Share R + epsilon is not R. It is boolean operation i.e. either you take R or you take epsilon. 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes i) has any number of 0's and iii) has any number of 0's so C is answer Murali answered Jul 13, 2015 Murali comment Share Follow See all 0 reply Please log in or register to add a comment.