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.1k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply junaid ahmad commented Sep 24, 2017 reply Follow Share Some of the regular expression equivalent to (a+b)* which might help (a+b)* =(a*+b*)* = (a*b*)* = (a*+b)* =(a+b*)* =a*(ba*)* =b*(ab*)* 27 votes 27 votes Nirmal Gaur commented Jan 13, 2020 reply Follow Share Remember that: If r is a regular expression denoting a language L(r) over some alphabet Σ, and we have Σ ⊆ L(r) then L((r)*) = Σ*. To see why, consider the regular expression (a*+ b) over the alphabet {a,b}. The language L((a*+ b)) contains both a and b as its strings and those two symbols alone are enough for the Kleene star to build all of {a, b}*, that is, L((a*+b)*) has all the strings that are present in L((a+b)*). Now similar thing is true for regular expressions like (a + b*)*, (a* + b*)* , (a*b*)*, All of them would represent (not generate) same set strings represented by (a+b)*. On the other hand, a regular expression like (a*b)* doesn't satisfy this. That's because L((a*b)) doesn't have a as one of its string (it does have b though, but that isn't sufficient). Same goes for regular expressions (ab*)*. Source: http://www.fbeedle.com/formallanguage/ch07.pdf 1 votes 1 votes Abhrajyoti00 commented Oct 19, 2022 i edited by Abhrajyoti00 Oct 20, 2022 reply Follow Share We can find a pattern easily → First find 0 bit strings → 1 bit strings → 2 bit → 3bit… They are exactly same:- $A = (01 + 1)^*$ $= \{\epsilon, 1,01,11,101, 111,011 \ ...\}$ $B = \left(\left(01\right)^*1^*\right)^*$ $ = \{\epsilon, 1,01,11, 101, 111,011 \ ...\}$ 0 votes 0 votes Ajitgate21 commented Oct 20, 2022 i edited by Ajitgate21 Oct 20, 2022 reply Follow Share A=(01+1)*=> {(01+1)^0,(01+1)^1,(01+1)^2...}=>L={e,01,1,011,101,11,0101,...}B=((01)*1*)*.=> (01)*=((01)^0,(01)^1,(01)^2)..)=>{e,01,0101..}1*={1^0,1^1,1^2,...}={e,1,11,111,..}{e,01,0101,1,0111,01111,1011,10111,0101111,...}*=L={(e)^*,(01)^*,(0101)^*…..}; (01,1)^2= (01)^01^1(01)^11^0=101 ANS:-D 0 votes 0 votes Abhrajyoti00 commented Oct 20, 2022 i edited by Abhrajyoti00 Oct 20, 2022 reply Follow Share @Ajitgate21 We can get $101$ in $B$ also.$B = \left(\left(01\right)^*1^*\right)^* =\left(\left(01\right)^*1^*\right)^2 = \left(\left(01\right)^*1^*\right) \left(\left(01\right)^*1^*\right) = \left(\left(01\right)^01^1\right) \left(\left(01\right)^11^0\right)$$\implies 1^1(01)^1 = 101$Hence, Option D) $A = B$ is correct. 0 votes 0 votes 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.