edited by
11,110 views
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?

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

4 Answers

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$.

edited by
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

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

 

Answer:

Related questions

41 votes
41 votes
7 answers
1
Kathleen asked Sep 25, 2014
22,935 views
The string $1101$ does not belong to the set represented by$110^*(0 + 1)$$1(0 + 1)^*101$$(10)^*(01)^*(00 + 11)^*$$(00 + (11)^*0)^*$
29 votes
29 votes
5 answers
2
Arjun asked Oct 17, 2014
8,697 views
Give a regular expression for the set of binary strings where every $0$ is immediately followed by exactly $k$ $1$'s and preceded by at least $k$ $1$’s ($k$ is a fixed...
22 votes
22 votes
3 answers
4
Kathleen asked Sep 25, 2014
7,330 views
Formatting for a floppy disk refers toarranging the data on the disk in contiguous fashionwriting the directoryerasing the system datawriting identification information o...