Regular expression#previous year gate

Question

Give a regular expression for the set of binary strings where every $0$ is immediately followed by exactly $k$ number of $1's$ and preceded by at least $k$ number of $1's$ ($k$ is a fixed integer).Choose the correct one out of two.

1. $1^*1^k(01^k)^*1^*$       
2. $1^*(1^k01^k)^*$

Comments

None is  correct

 But option A .. would be .Correct if we remove 1* from last.

---

None is Correct Because of the " followed by exactly k number of 1's". Exactly K number of 1's means that Not more than K 1's, Not less than K 1's after Every Zero. 

Which Year GATE Question it is? I never came across it before. 

---

Yeah none of them is correct answer let's check option B,take k=2 acc. to option B 11011 11011 string can be generate but after 0 there are not exactly 2 1's.

---

yes thanks:)

Answer 1

None is Correct. The Correct Regular Expression for the language described, will be :

$1^* + 1^*1^k0(1^k0)^*1^k$

 The Condition is "followed by exactly k number of 1's". Exactly K number of 1's means that Not more than K 1's, Not less than K 1's after Every Zero. 

Because of this Condition, Only the First $0$ can be preceded by more than $k$ 1's. All the other Zeroes (i.e. Except the First Zero) will be both Preceded and followed by Exactly $k$ 1's.

---

Note that If R and S are any Two RE then $R(SR)^*$ and $(RS)^*R$ Always denote the same language. Same logic can be applied here and the above RE can also be written as follows :

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

Credit : @Bhanukumar

Comments

Hello Sir,

     Is This one is Right or Not?

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

---

Yes. Correct @Bhanu

If R and S are any Two RE then $R(SR)^*$ and $(RS)^*R$ Always denote the same language. Same logic can be applied here also. I will update it in the answer. Thank you for mentioning.

---

@Deepakk Poonia Sir     @bhanu kumar 1

Can you please tell why * is added with (01^k) .I am confused why we have to add * for it. For no zero condition,we are already adding 1* .  Please explain

---

@ sutanay3

Please tell , is this String belongs to language or not According to Problem description : 

111011011011.