37 votes 37 votes If the regular set $A$ is represented by $A = (01 + 1)^*$ and the regular set $B$ is represented by $B = \left(\left(01\right)^*1^*\right)^*$, which of the following is true? $A \subset B$ $B \subset A$ $A$ and $B$ are incomparable $A = B$ Theory of Computation gate1998 theory-of-computation regular-expression normal + – Kathleen asked Sep 25, 2014 • edited May 15, 2018 by Milicevic3306 Kathleen 11.3k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Ajitgate21 commented Oct 20, 2022 reply Follow Share @Abhrajyoti00 (01+1)^2=(01+1)(01+1)=01(01+1)+1(01+1)={0101,011,101,11} 0 votes 0 votes Abhrajyoti00 commented Oct 20, 2022 reply Follow Share @Ajitgate21 Thanks, corrected it. We can generate $101$ from both $A$ and $B$. 0 votes 0 votes Ajitgate21 commented Oct 20, 2022 reply Follow Share @Abhrajyoti00 Thank you so much. 1 votes 1 votes Please log in or register to add a comment.
Best answer 41 votes 41 votes Correct Option: D Both generates all strings over $\{0,1\}$ where a $0$ is immediately followed by a $1$. Arjun answered Oct 16, 2014 • edited May 6, 2021 by soujanyareddy13 Arjun comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Arjun commented Nov 10, 2014 reply Follow Share Lexicographic ordering of the strings over {0, 1} is {ϵ, 0, 1, 00, 01, 10, 11, 000, 001, ....}. You can see if these strings are generated by the given regular expressions- its like trying out examples but quite useful in finding if regular expressions are equal. 7 votes 7 votes Priyansh Singh commented Aug 16, 2020 reply Follow Share Let’s take 01 as ‘a’ and 1 as ‘b’ now the expression looks like (a+b)* = (a*b*)* yes it is equal. 1 votes 1 votes Rutuja Desai commented Dec 2, 2021 reply Follow Share How will B be able to generate the string ‘101’, which A is able to generate ?? 0 votes 0 votes Please log in or register to add a comment.
18 votes 18 votes (a*b*)* = ( ^ + a + aa +aaa+ .. .+ b+ bb+bbb+....+ ab+abb+....+aab+aabb +)* =(a+b +..rest...+..)* = (a+b)* [all combinations (or that of rest) are included in (a+b)*] In given problem ((01)*1*)* = (01+1)* So, A = B Praveen Saini answered Mar 5, 2015 Praveen Saini comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments vishalshrm539 commented Dec 21, 2017 reply Follow Share what about "101"...? 0 votes 0 votes Praveen Saini commented Dec 23, 2017 reply Follow Share $101 $ $((01)^*1^*)^* \Rightarrow ((01)^*1^*)((01)^*1^*) \Rightarrow (\epsilon1)((01)\epsilon ) \Rightarrow 101$ 6 votes 6 votes vishalshrm539 commented Dec 23, 2017 reply Follow Share thanks sir 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes (a+ b)* = (a*+b*)* = (a*b*)* = (a* + b)* = (a + b*)* = a*(ba*)* = b*(ab*)* Now, A= (01 + 1)* , B = ((01)* 1*)* B = ((01)* 1*)* = ( (01)* 1*)* a = 01, b = 1 = (a*b*)* = (a + b)* = (01 + 1)* = A Option : D faisal_sayyed answered Jan 13, 2022 faisal_sayyed comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Option d, A = B A = (01 + 1)* B = ((01)*1*)* = ((01)* + 1*)* = (01 + 1)* = A manikantsharma answered Aug 20, 2022 manikantsharma comment Share Follow See all 0 reply Please log in or register to add a comment.