The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+18 votes
1.3k 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$
asked in Theory of Computation by Veteran (59.6k points)
edited by | 1.3k views
+4

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

3 Answers

+21 votes
Best answer

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

answered by Veteran (358k points)
edited by
0

generally:

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

+11

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

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

answered by Veteran (55.3k points)
0
What about the string 01101 ?
(01 + 1)* -> generates.

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

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

$((01)^*1^*)^* \Rightarrow ((01)^*1^*)((01)^*1^*) \Rightarrow ((01)1)((01)\epsilon ) \Rightarrow 01101$
0
what about "101"...?
+1
$101 $

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

       (r + s)* = (r* + s*)* = (r*s*)* .You can solve this regular expression. i.e,answer will be d

answered by Active (3k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,771 questions
47,479 answers
145,666 comments
62,241 users