in Theory of Computation edited by
6,597 views
26 votes
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)
in Theory of Computation edited by
by
6.6k views

4 Comments

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

 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
0
Thnx
0
0

5 Answers

53 votes
53 votes
Best answer
$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

4 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.
1
1

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

3
3

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

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

4 Comments

is it a valid regular expression?
0
0

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

how is this one correct?

3
3
@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}\,)^*$
2
2
suppose k=2 then valid string 1 can not be generated by given RE . plz correct me !!
1
1
8 votes
8 votes
(1*1^k(01^k)*) * +  1*

plz correct me !!

2 Comments

CORRECT!
0
0

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*1k(01k)*+1*

3
3
4 votes
4 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.

3 Comments

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

is this wrong?
0
0
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 .
2
2
yes u are correct!
0
0

Related questions