21 votes 21 votes Let $r, s, t$ be regular expressions. Which of the following identities is correct? $(r + s)^* = r^*s^*$ $r(s + t) = rs + t$ $(r + s)^* = r^* + s^*$ $(rs + r)^* r = r (sr + r)^*$ $(r^*s)^* = (rs)^*$ Theory of Computation tifr2010 theory-of-computation regular-expression + – makhdoom ghaya asked Oct 10, 2015 edited May 15, 2018 by Milicevic3306 makhdoom ghaya 2.6k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply `JEET commented Dec 6, 2019 reply Follow Share This question was repeated in $\mathbf{2015}$ as well. 0 votes 0 votes `JEET commented Dec 6, 2019 reply Follow Share https://gateoverflow.in/29861/tifr2015-b-7 1 votes 1 votes Please log in or register to add a comment.
Best answer 24 votes 24 votes $(r + s)^* = r^*s^*$ LHS can generate '$sr$' but RHS not $r(s + t) = rs + t$ LHS can generate '$rt$' but RHS not $(r + s)^* = r^* + s^*$ LHS can generate '$sr$' but RHS not $(rs + r)^* r = r (sr + r)^*$ They are equivalent $(r^*s)^* = (rs)^*$ LHS can generate '$rrrs$' but RHS not So option D is correct answer. Umang Raman answered Oct 8, 2015 edited Mar 5, 2018 by kenzou Umang Raman comment Share Follow See all 5 Comments See all 5 5 Comments reply Deepesh Kataria commented Nov 15, 2015 reply Follow Share WHY NOT C option .....correct ...explain –1 votes –1 votes Umang Raman commented Nov 15, 2015 reply Follow Share i think i have given the reason 'sr' can be generated from LHS but not RHS 1 votes 1 votes Sachin Mittal 1 commented Dec 28, 2017 reply Follow Share Hint for Option D - $(rs + r)r= (rsr + rr) = r(sr+r)$ (post multiply and then pre common ) can u take it from here ? 14 votes 14 votes Abhijit Sen 4 commented Mar 4, 2018 reply Follow Share Hi I have a doubt here. (r+s)∗= can generate sr Can you explain how (r∗s∗)* generates sr In other words how they are equivalent (r+s)∗=(r∗s∗)* 0 votes 0 votes Abhijit Sen 4 commented Mar 4, 2018 reply Follow Share Hi..Please ignore..I got the answer. 0 votes 0 votes Please log in or register to add a comment.
6 votes 6 votes Option D is a right choice. HeadShot answered Sep 4, 2018 HeadShot comment Share Follow See all 4 Comments See all 4 4 Comments reply chauhansunil20th commented Nov 2, 2018 reply Follow Share perfect! 0 votes 0 votes Adarsh Pandey commented Oct 20, 2019 reply Follow Share whats X ...? 0 votes 0 votes chirudeepnamini commented Nov 27, 2019 reply Follow Share @Adarsh Pandey He took (s+epsilon) as X.. Which is just a variable.. 0 votes 0 votes vishnu_m7 commented Nov 7, 2020 reply Follow Share How does the given identity at the end hold? It should be (pq)*p=p*(qp). 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes https://gateoverflow.in/29861/tifr2015-b-7 Pritam Dutta answered Dec 16, 2017 Pritam Dutta comment Share Follow See all 0 reply Please log in or register to add a comment.