NIELIT 2016 MAR Scientist C - Section C: 17

Question

Regular expression $(a \mid b)(a \mid b)$ denotes the set

• A. $\{a,b,ab,aa\}$
• B. $\{a,b,ba,bb\}$
• C. $\{a,b\}$
• D. $\{aa,ab,ba,bb\}$

Comments

D is the correct option.

---

Option D

Answer 1

Given regular expression is $(a | b)(a | b)$.

This translates to picking either a or b followed by either a or b, which means the strings that the above regular expression would generate are ${aa, ab, ba, bb}$.

$\therefore$ Option D is correct.

Answer 2

Given regular expression can be written as:

$L=(a+b)(a+b)=(a+b)^2$,which accept all the strings of $a,b$ whose length is exactly $2.$

so $L=(a+b)^2=(\ aa,\ ab, \ ba,\ bb)$

Option A) wrong because it generates one length string like $a,b$ and $ba,bb$ is missing.

Option B) same explanation as A, and $aa,ab$ is missing.

Option C) wrong, produces one-length strings.

Option D) correct.

So Option $D$ is correct.

Note: in regular expression $+$ or $|$ sign represent concatenation. Concatenation provides a choice between strings.

Answer 3

Option D: $\{aa,ab,ba,bb\}$

---

here (a | b) (a | b), clearly it will have length of 2 so you can easily eliminate all the options other than D.

Also here (a | b) is equivalent to (a+b) i.e. either a or b.

So, (a | b)(a | b) can only produce: ‘aa’, ‘ab’, ‘ba’ and ‘bb’.