9,056 views

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?

1. $A \subset B$
2. $B \subset A$
3. $A$ and $B$ are incomparable
4. $A = B$

(01+1)^2=(01+1)(01+1)=01(01+1)+1(01+1)={0101,011,101,11}

@Ajitgate21 Thanks, corrected it. We can generate $101$ from both $A$ and $B$.

@Abhrajyoti00 Thank you so much.

Correct Option: D

Both generates all strings over $\{0,1\}$ where a $0$ is immediately followed by a $1$.

by

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.

Let’s take  01 as ‘a’ and 1 as ‘b’

now the expression looks like

(a+b)* = (a*b*)*

yes it is equal.

How will B be able to generate the string ‘101’, which A is able to generate ??

(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

$101$

$((01)^*1^*)^* \Rightarrow ((01)^*1^*)((01)^*1^*) \Rightarrow (\epsilon1)((01)\epsilon ) \Rightarrow 101$
thanks sir

(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

Option d, A = B

A = (01 + 1)*

B = ((01)*1*)* = ((01)* + 1*)* = (01 + 1)* = A