GATE Computer Science Engineering(CSE) 2027 Test: Regular Expressions

Set of all binary strings having two consecutive 0s and two consecutive1s

Anything 00 Anything 11 Anything + Anything 11 Anything 00 Anything

And it is same after taking common.

Neither they said Both are immediate nor they give a predefined order, so it should be as above

to know the ans let us check all the options.

strings generated by S are any numbers of 1's followed by one 0, i.e., 10,110,1110,1110,......) Strings generated by r are is 1 followed by any combination of 0 or 1, i.e., 1,10,11,1110,101,110,.....This shows that all the strings that can be generated by S,can also be generated by r it means 

  here strings generated by t are any numbers of 1 (here 1* means we have strings as    followed by only one 0, i.e., 0,10,110,1110,.....So we can see that all the strings that are present in S can also be
generated by t, hence    which shows that option A is true.

  this is false because string 1 which can be generated by r, cannot be generated by S

Same as option A.

. this is false because string 0 which can be generated by t ,cannot be generated by S .

(a) is the answer

(b) RHS generates ∑* while LHS can't generate strings where r comes after s like sr,srr etc. LHS ⊂ RHS.

(c) LHS generates ∑* while RHS can't generate strings where r comes after an S. RHS  ⊂ LHS.

(d) LHS contains all strings where after an s, no r comes. RHS contains all strings of eitherr or s but no combination of them. So, RHS ⊂ LHS.

It has to be started by a letter followed by any number of letters and digits.

you can have any no. of 0's as well as null.
A is false because you cannot have single 0 in ii). same for option B. In D you are forced to have single 0 in iv) whereas not in iii).

D is correct.

Any string matched by (1+01)*(ε+0) contains no occurrence of 00. The subexpression (1+01) produces only the blocks 1 and 01, so every zero coming from these blocks is immediately followed by a one. The trailing (ε+0) allows at most one final zero. Hence two consecutive zeros cannot occur.

Conversely, take any binary string that does not contain 00. Every zero in such a string is either followed by a one (so can be grouped as 01) or is the final symbol (a single terminal 0). All remaining symbols are 1. Thus the string can be decomposed into a concatenation of 1 and 01 blocks, possibly followed by a single 0, showing it belongs to (1+01)*(ε+0).

Therefore (1+01)*(ε+0) denotes exactly the set of binary strings with no substring 00.

A = 0*(1+0)* equals {0,1}* and so includes strings with 00, so it is incorrect.

B = 0*1010* cannot generate the string 0, so it cannot represent the full set of strings without 00.

C = 0*1*01* cannot generate the string 1, so it is incorrect.

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

Only (a) and (b) can generate 1101.

R.E of option C won’t generate 1101 as you can see the language will contain L(C) = {epsilon,10,1010,1001,0101,00,11,0011,1100,………..}
Also, R.E of option D has ‘1’ but here two ’11’ are together hence its impossible to generate 1101.L(D) = {Epsilon,0,00,110,11110,11000,…………….}

Both generates all strings over ∑ .

(A) is the answer. Both (A) and the given expression generates all strings over ∑ .

(B) doesn't generate 11

(C) doesn't generate 11

Infinite set (because of *) of finite strings. A string is defined as a FINITE sequence of characters and hence can never be infinite. 

A) (a* + b* + c*)*  = ( ^ + a+aa+.. ..+b+bb+...+c+cc...)* = (a+b+c+ aa+..+bb+..+cc+..)*= (a+b+c)*  [any combination of rest of aa ,bb,cc, etc already come in (a+b+c)* ]

(a*b*c*)* = (a*+b*+c* +a*b*+b*c*+a*c*+..)*= (a+b+c+....)* = (a+b+c)*

((ab)* + c*)* =(ab+c+^+abab+...)* = (ab+c)*

(a*b* + c*)* = (a*+b*+c*+...)* =(a+b+c+..)* = (a+b+c)*

Say s1, s2 , s3 and t are states (in sequence)

s1 is start state
s1= ^ + s1a + s1b = ^+s1(a+b) = (a+b)* [using arden's theorem  R= Q+RP , then R= QP*][^ bcoz of start state]
s2 = s1a = (a+b)*a

s3= s2a+s2b = s2(a+b) = (a+b)*a(a+b)

t= s3b= (a+b)*a(a+b)b

t is final state so regular expression is (a+b)*a(a+b)b

R = (a+b)*(aa+bb)(a+b)*

having NFA

Equivalent DFA :

which is equivalent Transition graph [ by removing transition from q1 to q2 and q2 to q1 but does not effect on language ..be careful ]

That is equivalent to 

which is equivalent to 

which is equivalent to 

so equivalent regular expression is [a(ba)*(a+bb) + b(ab)*(b+aa)](a+b)* so option C is answer.

A) with at least 2 consecutive 1's, any no of 0's and any no of 1's

B) exactly two consecutive 1's

C)exactly two 1's but need not be consecutive

D) any no of 1's and 0's with at least two 1's

Counter example for other choices:

(A) 1010 is accepted which doesn't contain 00

(B) 000 is accepted

(D) 01 is not accepted

(A) - If the string contains a 1, it must end in a 1 hence cannot generate all bit strings with even number of 1's (eg, 1010)
(B) - is the answer
(C) - between the second and third 1's a 0 is not allowed (eg, 011011)

(D) - 00 is not allowed, zero is an even number.

(B) is the answer. (II) doesn't generate 11011 which is accepted by the given DFA

a. (r + s)* = r*s*            LHS can generate 'sr' but RHS not

b. r(s + t) = rs + t          LHS can generate 'rt' but RHS not

c. (r + s)* = r* + s*       LHS can generate 'sr' but RHS not

d. (rs + r)* r = r (sr + r)*   They are equivalent

e. (r*s)* = (rs)*            LHS can generate 'rrrs' but RHS not

As, mentioned in the question, the regular expression must accept all strings of 0 and 1 but with even no of 1s (including no 1s). Hence, 00 must be in the language. Option a, b, c, d do not accept 00. Hence, option e is correct.