1.8k 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$
edited | 1.8k views
+9

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*)*

(d) $A=B$. Both generates all strings over $\{0,1\}$ where a $0$ is immediately followed by a $1$.

edited by
0

generally:

(0*1*)* = (1*0*)= 1+  0*

+15

(0*1*)= (1*0*)= (1+  0*)*

0
couldnt get it.plz explain
+3
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.

(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

0
What about the string 01101 ?
(01 + 1)* -> generates.

((01)*1*)* ->cannot generate.

Hence, B is a subset of A.
+3
$01101$

$((01)^*1^*)^* \Rightarrow ((01)^*1^*)((01)^*1^*) \Rightarrow ((01)1)((01)\epsilon ) \Rightarrow 01101$
0
+2
$101$

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

1
2