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 1∗1k(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.
@akash.dinkar12 @manu00x @Bikram Sir, why there's a +1* in the given R.E?
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".
if i dont have 0 , it can have any number of 1's..1^k is not necessary..
how is this one correct?
According to ur soln
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*
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.
1*1k(0 1k)* + 1* should be the required RE