in Theory of Computation edited by
9,056 views
36 votes
36 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?

  1. $A \subset B$
  2. $B \subset A$
  3. $A$ and $B$ are incomparable
  4. $A = B$
in Theory of Computation edited by
9.1k views

4 Comments

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

0
0

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

0
0

@Abhrajyoti00 Thank you so much.

1
1

4 Answers

39 votes
39 votes
Best answer

Correct Option: D

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

edited by
by

4 Comments

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
7

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

now the expression looks like 

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

yes it is equal.

1
1
How will B be able to generate the string ‘101’, which A is able to generate ??
0
0
17 votes
17 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

4 Comments

what about "101"...?
0
0
$101 $

$((01)^*1^*)^* \Rightarrow ((01)^*1^*)((01)^*1^*) \Rightarrow (\epsilon1)((01)\epsilon ) \Rightarrow 101$
5
5
thanks sir
0
0
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

 

0 votes
0 votes
Option d, A = B

A = (01 + 1)*

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

Related questions