Back to the 2023 paper

Module 1: Introduction & Regular Languages

20232m

The string 11011101 does not belong to the set represented by:

(i) 1∗0∗(0+1)1^* 0^* (0+1)
(ii) 1(0+1)∗1011(0+1)^*101
(iii) (1(0)∗(0+1)∗(0+1))∗(1(0)^*(0+1)^*(0+1))^*
(iv) {00+(11)∗0}∗\{00 + (11)^*0\}^*

Worked SolutionAI Assisted

Answer

Correct Option: (iv) {00+(11)∗0}∗\{00 + (11)^*0\}^*

Explanation

Test w=1101w=1101 against each regex:

(i) 1∗0∗(0+1)1^*0^*(0+1): = 1∗1^* then 0∗0^* then single 00 or 11. 1101=11⏟1∗0⏟0∗1⏟(0+1)1101 = \underbrace{11}_{1^*} \underbrace{0}_{0^*} \underbrace{1}_{(0+1)} → belongs.

(ii) 1(0+1)∗1011(0+1)^*101: Must start with 11 and end with 101101. 1101=11⏟(0+1)∗1011101 = 1 \underbrace{1}_{(0+1)^*}101? Actually 11011101 = 11 + ϵ\epsilon + 101101 with middle 11? 1(0+1)∗101=1 x 1011(0+1)^*101 = 1\,x\,101 where x=0x=0? For w=1101w=1101, x=0x=0? Wait 1+0+101=11011+0+101 =1101 exactly, so w=1⋅0⋅101w = 1\cdot0\cdot101? No 1⋅101=11011\cdot101 =1101 with x=ϵx=\epsilon? 1(0+1)∗=11(0+1)^* =1, remaining 101=101101 =101 → 11011101 → belongs.

(iii) (1(0)∗(0+1)∗(0+1))∗(1(0)^*(0+1)^*(0+1))^*: This is essentially Σ∗\Sigma^* variant (can generate any string) → belongs.

(iv) {00+(11)∗0}∗\{00 + (11)^*0\}^*: Generators: 0000 (ends 0) and (11)∗0(11)^*0 = even 1's followed by 0, also ends 0. Any concatenation of blocks ending in 0 always ends in 0. 11011101 ends in 1 → does not belong.

Final Answer

$1101
otin {00 + (11)^0}^$ → Option (iv).

Similar questions

Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.