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^{*})^{*}

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+18 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?

- $A \subset B$
- $B \subset A$
- $A$ and $B$ are incomparable
- $A = B$

+19 votes

Best answer

+9 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

What about the string 01101 ?

(01 + 1)* -> generates.

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

Hence, B is a subset of A.

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

$((01)^*1^*)^* \Rightarrow ((01)^*1^*)((01)^*1^*) \Rightarrow ((01)1)((01)\epsilon ) \Rightarrow 01101$

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,079 questions

45,571 answers

132,066 comments

49,040 users