The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+11 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)
asked in Theory of Computation by Veteran (406k points)
edited by | 1.5k views
Thanks :) But that regular expression has a problem - it is EXACTLY k 1's after every 0.

why can't (01k)* + (1k1*0)* ???????


your First part (01)k produce 010101 if k=3, which shouldn't be part of the language.


Not just for this question, but for any of RE, DFA, PDA etc. Information in questions is like every  0  should be followed by exactly 2 '1'.

Whenever you read such statement wait for a second and think in terms of logic If '0' -> two '1'. Now we have to make DFA/RE keeping this implication true.

case 1: LHS is true, then RHS mus t be true hence 11k(01k)

case 2: If LHS is false, still our implication is true i.e no 0 is allowed hence 1*

Now why to use above method? Just to void corner cases like 1*. We all go with the flow satisfying giving criteria but missing other one.

Hope it helps.

5 Answers

+24 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.
answered by Boss (41k points)
edited by
let k = 2, 1101111 is a string generated here, but 0 is not followed by exactly 2 1's.
You are correct, updated.
I think given RE won't accept valid string 110111 for k=2
@Rajesh that's not a valid string

@Bikram sir

Please select this as the best answer.

@akash.dinkar12 @manu00x @Bikram Sir, why there's a +1* in the given R.E?

plz make a dfa for it!!
DFA can be made once $k$ is known.
Sir actually m not getting why +1* is added ??
The expression should work for any given $k$. Say $k=2$, now the expression must accept empty string, 1, 11 etc. For this reason $1^*$  is added.
Did yu mean the case where there is no  0 but 1(or more 1's)are there?
Yes. Exactly.
Got it Sir ..thanx
Also, Condition is "preceded by at least k 1's but more can be present so we need extra 1's that also why we need 1* in front".
$(1^* 1^k 0 1^k)^*  + 1^*$

is this wrong?

suppose k = 2 Gate Fever 


first 0 is followed by four 1's


yes i got it

it should be 1*1k(01k)*+1*


@Arjun @Bikram sir

Also, Condition is "preceded by at least k 1's but more can be present so we need extra 1's that also why we need 1* in front".

+8 votes
The expression will be of the form $1^*1^k(01^k)^*$.
answered by Active (4.1k points)
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 !!
+6 votes
(1*1^k(01^k)*) * +  1*

plz correct me !!
answered by Boss (23.4k points)


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*

+2 votes



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.

answered by Active (1.7k points)
(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!
0 votes

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

answered by Active (1.1k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,541 questions
54,083 answers
70,992 users