NIELIT 2017 DEC Scientist B - Section B: 2

Question

According to the given language, which among the following expressions does it correspond to ?

Language $L=\{x\in\{0,1\}\mid x\text{ is of length 4 or less}\}$.

• A. $(0+1+0+1+0+1+0+1)^4$
• B. $(0+1)^4$
• C. $(01)^4$
• D. $(0+1+\varepsilon)^4$

Comments

D is the correct answer.

---

option D because of empty string .

Answer 1

Given that,  $L=\{x\in \{0,1\}|x\; \text{is length 4 or less}\}$

$\text{Expression (E)} =$ Length $4$ or less means, length $0$ or length $(1)$ or length $(2)$ or length $(3)$ or length $4$

$E = \varepsilon + (0+1)^{1} + (0+1)^{2}+(0+1)^{3} + (0+1)^{4} = (\varepsilon+0+1)^{4}$

So, the correct answer is $(D).$

References:

• https://www.cs.odu.edu/~toida/nerzic/390teched/regular/reg-lang/examples.html
• https://web.stanford.edu/class/archive/cs/cs103/cs103.1132/lectures/15/Small15.pdf

Answer 2

When length is less than or equal to n then regular expression is $(0+1+ epsilon)^n$

Why epsilon is needed? Else we will get only strings of length n.

So D is correct.

Answer 3

$\text{option A, B, C does not generate minimal string of length 0 --- } \epsilon$

hence option D is correct answer

Answer 4

The extended notation would be (0+1)4 but however, we may allow some or all the factors to be ε. Thus ε needs to be included in the given regular expression.

correct option -D