The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+11 votes
1.5k views
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
+1
Thanks :) But that regular expression has a problem - it is EXACTLY k 1's after every 0.
0

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

0

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

+2

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

@Bikram sir

Please select this as the best answer.
0

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

0
plz make a dfa for it!!
0
DFA can be made once $k$ is known.
0
Sir actually m not getting why +1* is added ??
+1
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.
0
Did yu mean the case where there is no  0 but 1(or more 1's)are there?
0
Yes. Exactly.
0
Got it Sir ..thanx
0
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".
0
$(1^* 1^k 0 1^k)^*  + 1^*$

is this wrong?
+1

suppose k = 2 Gate Fever 

1101111011 

first 0 is followed by four 1's

0

yes i got it

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

0

@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)
0
is it a valid regular expression?
+2

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

how is this one correct?

+2
@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}\,)^*$
+1
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)
0
CORRECT!
+2

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*

+2 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.

answered by Active (1.7k points)
0
(1* 1^k 0 1^k)* + 1*

is this wrong?
+1
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 .
0
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
187,206 comments
70,992 users