edited by
8,697 views
29 votes
29 votes
Give a regular expression for the set of binary strings where every $0$ is immediately followed by exactly $k$ $1$'s and preceded by at least $k$ $1$’s  ($k$ is a fixed integer)
edited by

5 Answers

Best answer
54 votes
54 votes
$1^*1^k(01^k)^* + 1^*$

This is correct expression, this considering chance of not having any $0$'s (In that case string can also be empty string ).

PS: The question assumes a fixed $k$, and we should expand the given expression for that $k$ to get a valid regular expression.
edited by
9 votes
9 votes
(1*1^k(01^k)*) * +  1*

plz correct me !!
8 votes
8 votes
The expression will be of the form $1^*1^k(01^k)^*$.
5 votes
5 votes

 

11k(01k)+1∗  

is correct answer for this because if even a single 0 come's then then next zero if any must come at a distance of k consecutive 1;s otherwise it will violate the property that a zero should be followed by exactly k 0's .thus all 0's must be at a distance of k 1's exactly. lso if no 0 is there then there is no constraint so 1* is added.

Related questions

41 votes
41 votes
7 answers
1
Kathleen asked Sep 25, 2014
22,936 views
The string $1101$ does not belong to the set represented by$110^*(0 + 1)$$1(0 + 1)^*101$$(10)^*(01)^*(00 + 11)^*$$(00 + (11)^*0)^*$
37 votes
37 votes
4 answers
2
Kathleen asked Sep 25, 2014
11,110 views
If the regular set $A$ is represented by $A = (01 + 1)^*$ and the regular set $B$ is represented by $B = \left(\left(01\right)^*1^*\right)^*$, which of the following is t...
23 votes
23 votes
3 answers
3
Kathleen asked Sep 25, 2014
6,326 views
Which of the following statements is false?Every finite subset of a non-regular set is regularEvery subset of a regular set is regularEvery finite subset of a regular set...