retagged by
2,409 views
0 votes
0 votes

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}\}$.

  1. $(0+1+0+1+0+1+0+1)^4$
  2. $(0+1)^4$
  3. $(01)^4$
  4. $(0+1+\varepsilon)^4$
retagged by

6 Answers

3 votes
3 votes

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:

edited by
1 votes
1 votes
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.
0 votes
0 votes
$\text{option A, B, C does not generate minimal string of length 0 --- } \epsilon$

hence option D is correct answer
0 votes
0 votes
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
Answer:

Related questions

1 votes
1 votes
3 answers
1
1 votes
1 votes
4 answers
2
0 votes
0 votes
2 answers
3
admin asked Mar 30, 2020
699 views
Which of the following regular expression is equal to $(r_1+r_2)^*$?$r_1^*r_2^*$$(r_1r_2)^*$$r_1^*r_2^*+r_1r_2$$(r_1^*r_2^*)^*$
1 votes
1 votes
2 answers
4
admin asked Mar 30, 2020
1,252 views
Which of the following is equivalent regular expressions?$((01)^*(10)^*)^*$$(10+01)^*$$(01)^*+(11)^*$$(0^*+(11)^*+0^*)^*)$(i) and (ii)(ii) and (iii)(iii) and (iv)(iv) and...