## CMI 2021

Question 1 |

If the milkman doesn’t deliver milk or the geyser doesn’t work, then Akash will be late for school and lunch will be cooked late. Suppose lunch was actually cooked on time. Which of the following is definitely true?

Akash was late for school | |

Akash reached school in time | |

Geyser worked | |

Milkman did not deliver milk |

Question 1 Explanation:

If either the milkman doesn’t deliver milk or the geyser doesn’t work, then (in partic-
ular) lunch will be cooked late. But lunch was actually cooked on time. So it follows
that the milkman delivered on time and the geyser actually worked. So option (c) is
definitely true, and option (d) is definitely false. Akash can either be a dutiful student
and reach school on time, or be lazy and not go to school on time. So neither (a) nor
(b) can be asserted for certain.

Question 2 |

Let L be the language over {a, b} that contains the same number of occurrences of a and b. Which of the following languages is regular?

L ∩ a* b | |

(L ∩ a* b*) ∪ a* b | |

L ∪ a* b | |

(L ∩ a* b*) ∪ b* a |

Question 2 Explanation:

Answer: (b) (L ∩ a* b*) ∪ a* b*

(a) L ∩ a∗ b∗ = {a

(b) (L ∩ a* b*) ∪ a* b* = {a

(c) If L3 = L ∪ a* b* were regular, then L3 ∩ b* a* would also be regular. But L3 ∩ b* a* is {ba

(d) If L4 = (L ∩ a* b* ) ∪ b* a* were regular, then L4 ∩ a* b* would also be regular. But L4 ∩ a* b* is {a

(a) L ∩ a∗ b∗ = {a

^{n}b^{n}| n ≥ 0} is not a regular language.(b) (L ∩ a* b*) ∪ a* b* = {a

^{m}b^{n}| m, n ≥ 0} is a regular language.(c) If L3 = L ∪ a* b* were regular, then L3 ∩ b* a* would also be regular. But L3 ∩ b* a* is {ba

^{n}| n ≥ 0}, which is not regular.(d) If L4 = (L ∩ a* b* ) ∪ b* a* were regular, then L4 ∩ a* b* would also be regular. But L4 ∩ a* b* is {a

^{n}b^{n}| n ≥ 0}, which is not regular.Question 3 |

Which of the following regular expressions represents binary strings that are multiples of 3? Note that we consider the leftmost bit to be the most significant.

((11)0*)* | |

1(01*)* | |

(10*)* | |

(11 + 101*01 + 0)* |

Question 3 Explanation:

Let L(r) denote the language represented by the regular expression r.

(a) It can be checked that L(((11)0*)*) does not contain the string 1001, which represents 9.

(b) L((10*)*) contains 1, which represents a non-multiple of 3.

(c) L(1(01*)*) contains 101 (representing 5), as also 1 (representing 1).

(d) This is the only remaining option. One can prove it by first constructing a DFA for binary strings that are multiples of 3 and converting it to a regular expression.

(a) It can be checked that L(((11)0*)*) does not contain the string 1001, which represents 9.

(b) L((10*)*) contains 1, which represents a non-multiple of 3.

(c) L(1(01*)*) contains 101 (representing 5), as also 1 (representing 1).

(d) This is the only remaining option. One can prove it by first constructing a DFA for binary strings that are multiples of 3 and converting it to a regular expression.

Question 4 |

Consider the following statements about finite simple graphs G:

(i)If each vertex of a graph G has degree at least 2 then G contains a cycle as a subgraph.

(ii)If the number of edges of a graph G is at least as large as the number of its vertices, then G contains a cycle as a subgraph.

Which of the above two statements holds for all graphs?

(i)If each vertex of a graph G has degree at least 2 then G contains a cycle as a subgraph.

(ii)If the number of edges of a graph G is at least as large as the number of its vertices, then G contains a cycle as a subgraph.

Which of the above two statements holds for all graphs?

(i) only | |

(ii) only | |

both (i) and (ii) | |

neither of them |

Question 4 Explanation:

(i) Let P = ⟨v1, v2, . . . , vt⟩ be a maximal path in G. Since vt has degree at least 2 in G, there is an edge {vt, x} in G which is different from the edge incident on vt in the path P. Since P is a maximal path the vertex x must belong to P. So x = vi for some 1 ≤ i < (t − 1). The path ⟨vi, v(i+1), . . . , vt⟩ together with the
edge {vt, vi} forms a cycle in G.

(ii) Suppose not, and let H be a graph with the smallest number of vertices which contradicts the statement. That is, H has at least as many edges as vertices, and does not contain a cycle. From the solution to part (a) above we get that there must be a vertex v in H whose degree is at most one. Deleting v from H results in a graph H′ with

(i) one fewer vertex, and

(ii) at most one fewer edge, so H′ also satisfies the premise of the statement.

But then H′ does not have any cycle, because H did not have any by assumption. Thus H′ is a graph with fewer vertices than H for which the statement holds, which contradicts our assumption about H. Hence proved.

(ii) Suppose not, and let H be a graph with the smallest number of vertices which contradicts the statement. That is, H has at least as many edges as vertices, and does not contain a cycle. From the solution to part (a) above we get that there must be a vertex v in H whose degree is at most one. Deleting v from H results in a graph H′ with

(i) one fewer vertex, and

(ii) at most one fewer edge, so H′ also satisfies the premise of the statement.

But then H′ does not have any cycle, because H did not have any by assumption. Thus H′ is a graph with fewer vertices than H for which the statement holds, which contradicts our assumption about H. Hence proved.