edited by
22,132 views
68 votes
68 votes

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

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

10 Answers

Best answer
75 votes
75 votes
  1. - If the string contains a $1$, it must end in a $1$ hence cannot generate all bit strings with even number of $1$'s (eg, $1010$)
  2. - is the answer
  3. - between the second and third $1$'s a $0$ is not allowed (eg, $011011$)
  4. - $00$ is not allowed, zero is an even number.
edited by
31 votes
31 votes
(A) ( 0 * 10 * 1) * --->0110(valid string) not possible to produce from this Regular Expression.

(B) 0 * (10 * 10 *) * ---> Produces all strings with even number of 1's.

(C) 0 * (10 * 1 ) * 0 * ----> 11011(valid string) cannot be produced from this.

(D) 0 * 1 (10 * 1) * 10 ---> epsilon or 0 (valid strings) can not be produced.( even number of 1's includes zero number of 1's)

Therefore Answer : B Correct.
edited by
10 votes
10 votes

 method 1: draw the DFA and then derive reg ex from it 

   

method 2: by verification 

option a. does n't generates strings ending with 0 ex:1100

option c :does n't generates strings like 110011,1101111,011011,...i.e it does n't producing 0 between 2nd 1 and 3rd 1 in the string

option d: does n't generate $\epsilon$ 

option b: is the answer

edited by
1 votes
1 votes
We can omit out A because it cannot generate strings ending with 0 like 00

Omit D bcoz it cannot generate epsilon

now for B and C .we can clearly observe that C is a subset of B .Any language generated by C can be generated by B so B is the correct option.
Answer:

Related questions

62 votes
62 votes
9 answers
1
go_editor asked Sep 30, 2014
23,705 views
Let $w$ be any string of length $n$ in $\{0,1\}^*$. Let $L$ be the set of all substrings of $w$. What is the minimum number of states in non-deterministic finite automati...
40 votes
40 votes
1 answer
2