4,938 views
10 votes
10 votes

Let $L=\{w \in (0+1)^* \mid w \text{ has even number of 1's}\}$, i.e. $L$ is the set of all bit strings with even number of 1's. Which one of the regular expression below represents $L$?

  1. $(0^*10^*1)^*$
  2. $0^*(10^*10^*)^*$
  3. $0^*(10^*1^*)^*0^*$
  4. $0^*1(10^*1)^*10^*$

1 Answer

Best answer
25 votes
25 votes

 L is the set of all bit strings with even number of 1's.

a) (0*10*1)*          - It can not accept string 0110 ( I mean a string ends with 0 even if it contains even number of 1's ).

c) 0*(10*1*)*0*   - It can accept a string with odd number of 1's. For ex- 01011.

d) 0*1(10*1)*10* - It can not accept any string with zero number of 1's. For ex- 0, 00, 000 etc.

Ans-  b) 0*(10*10*)*

selected by
Answer:

Related questions

18 votes
18 votes
8 answers
1
Anu asked Jul 4, 2016
17,386 views
What is the highest type number that can be assigned to the following grammar?$$S\to Aa,A\to Ba,B \to abc$$Type 0Type 1Type 2Type 3
34 votes
34 votes
7 answers
3
Kathleen asked Sep 22, 2014
20,203 views
$$S \to aSa \mid bSb\mid a\mid b$$The language generated by the above grammar over the alphabet $\{a,b\}$ is the set of:all palindromesall odd length palindromesstrings t...
33 votes
33 votes
5 answers
4