GATE 2010
April 6, 2025GATE 2000
April 6, 2025GATE 2010
| Question 39 |
Let L = {w ∈ (0 + 1)* | w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?
| (0*10*1)* | |
| 0*(10*10*)* | |
| 0*(10*1*)*0* | |
| 0*1(10*1)*10* |
Question 39 Explanation:
The best way to find correct answer is option elimination method. We will guess strings which has even number of 1’s and that is not generated by wrong options OR which generate strings which doesn’t have even number of 1’s.
Option A: (reg expr: (0*10*1)* ) doesn’t generate string such as { 110, 1100,….}
Option C: (reg expr: 0*(10*1*)*0* generate string such as {1, 111,….} which have odd number of 1’s.
Option D: (reg expr: 0*1(10*1)*10* doesn’t generate strings such as { 11101, 1111101, ….}.
Option A: (reg expr: (0*10*1)* ) doesn’t generate string such as { 110, 1100,….}
Option C: (reg expr: 0*(10*1*)*0* generate string such as {1, 111,….} which have odd number of 1’s.
Option D: (reg expr: 0*1(10*1)*10* doesn’t generate strings such as { 11101, 1111101, ….}.
Correct Answer: B
Question 39 Explanation:
The best way to find correct answer is option elimination method. We will guess strings which has even number of 1’s and that is not generated by wrong options OR which generate strings which doesn’t have even number of 1’s.
Option A: (reg expr: (0*10*1)* ) doesn’t generate string such as { 110, 1100,….}
Option C: (reg expr: 0*(10*1*)*0* generate string such as {1, 111,….} which have odd number of 1’s.
Option D: (reg expr: 0*1(10*1)*10* doesn’t generate strings such as { 11101, 1111101, ….}.
Option A: (reg expr: (0*10*1)* ) doesn’t generate string such as { 110, 1100,….}
Option C: (reg expr: 0*(10*1*)*0* generate string such as {1, 111,….} which have odd number of 1’s.
Option D: (reg expr: 0*1(10*1)*10* doesn’t generate strings such as { 11101, 1111101, ….}.