The Gateway to Computer Science Excellence

+15 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)

+11

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^{∗}1^{k}(01^{k})^{∗}

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.

+30 votes

Best answer

+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

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

+8 votes

+6 votes

+2 votes

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.

52,345 questions

60,494 answers

201,847 comments

95,305 users