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.

Answer: (b) (L ∩ a* b*) ∪ a* b*
(a) L ∩ a∗ b∗ = {aⁿ bⁿ | n ≥ 0} is not a regular language.
(b) (L ∩ a* b*) ∪ a* b* = {a^m bⁿ | 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 ≥ 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 ⁿ bⁿ| n ≥ 0}, which is not regular.

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.

(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.