Dark Mode

6,597 views

26 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)

@ kuldeep chamoli in the question, where **every** 0 is immediately followed…..

So the string can have more than 1 zero right? But your regular expression contains a single 0.

0

53 votes

Best answer

1

The question says :-

every 0 is immediately followed by exactly k 1's and preceded by at least k 1’s (k is a fixed integer)

This means whenever a $0$ appears, **exactly** $k$ 1’s should be after that $0$ and **atleast** $k$ 1’s before that $0$. Eg: Let $k$ = $1$; $w$ = $110101$ is a correct string.

**Imp to note: **It **can’t be **$11011101$ as after $0$ three $1’s$ **can’t occur **as we took $k=1$.

Hence** correct regex** is : $1^*1^k(01^k)^* + 1^*$. With this we fix $(01^k)$ always so after $0$ exactly $k$ $1's$ will appear.

Taking your regex: $(1^k1^* 01^k) ^* + 1^*$, if we put $k = 1$ we will get $w = (1^{1}1^101^1)(1^{1}1^101^1) = 11011101$ which is a **wrong string.**

3

8 votes

2

8 votes

4 votes

1^{∗}1^{k}(01^{k})^{∗}+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.