GATE CSE 1998 | Question: 3b

Question

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)

Comments

Thnx

---

What about (1* (1^k 0)* 1^k) + 1*   ??
This just follows the same property but in the other order.

---

silly mistake done that i haven't consider that "preceded by atleast k 1's . But while analysing i've found that total regex i've written is wrong.

Answer 1

$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.

Comments

@Abhrajyoti00

Taking your regex: (1k1∗01k)∗+1∗, if we put k=1 we will get w=(1111011)(1111011)=11011101 which is a wrong string.

Extremely Thanks bro, got it now. 

---

is 1*(1^k(01^k)*) correct?

---

I also thought something like this but it would fail because  we would have at least k 1's in this case when there are no 0's in the string corresponding to the language. A union of 1* would take care of that.

Answer 2

(1*1^k(01^k)*) * +  1*

plz correct me !!

Comments

CORRECT!

---

WRONG!!

According to ur soln 

if k=2

then 1101111011 is getting accepted which should not be accepted; many other unwanted strings are accepted too! 

since every 0 should be followed by exactly k 1's;

correct one is  1^*1^k(01^k)*+1^*

---

This is extremely wrong just use the inductive definition of kleene closure to see whats wrong.

Answer 3

The expression will be of the form $1^*1^k(01^k)^*$.

Comments

suppose k=2 then valid string 1 can not be generated by given RE . plz correct me !!

---

I think this is wrong because, suppose that k is 5, and you wish to generate only 3 1's, then you won't be able to generate it as you will get at least 5 1's for sure.

---

if K is 5 either way I will have atleast 5 1's on both side of 0. what do you mean by you wish to generate only 3?

Answer 4

 

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.

Comments

(1* 1^k 0 1^k)* + 1*

is this wrong?

---

Ya this is incorrect because it violates the property that every zeroes must be followed by exactly k 1's if you write the first term twice then you will see that this property fails .

---

yes u are correct!

Answer 5

1^*1^k(0 1^k)^* + 1^*    should be the required RE

Answer 6

We need to make sure that if a zero has appeared then after that only 1^k is only possible and nothing else as a result of that block keeps on repeating.