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

Can anyone what's wrong in (1+e)^k0(1)^k here? pls

---

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

---

Thnx

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

Here the question says every 0 is preceded by very 0 is immediately followed by exactly k 1's and preceded by at least k 1’s.

So, does it mean every 0 preceded at least k 1s??

then (1^k1^* 01^k) ^* + 1^* should be the answer.

please explain.

---

@Argharupa Adhikary

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.

---

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

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^*

Answer 3

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

Comments

is it a valid regular expression?

---

if i dont have 0 , it can have any number of 1's..1^k is not necessary..

how is this one correct?

---

@Raunak: No, not right now. However, that is because we don't know the value of $k$. Once we know the value of $k$, we will re-write the Regular Expression.

For example, if $k=3$, we will re-write the regular expression as: $1^*\,\underbrace{111}_{k=3}\,(0\,\underbrace{111}_{k=3}\,)^*$

---

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

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!