TOC - Doubt

Question

Consider these statements:
S1: If a language is infinite, it has to be non-Regular.
S2: Let L be any language.
$(\overline{L})^{*} \neq (\overline{L^{*}})$

(a) Both are True
(c) S1 → True, S2 → False
(b) Both are False
(d) S1 → False, S2 → True

Comments

Both are fasle

Answer 1

$S_1$ is false. The counter example is a very popular regular language - $(a+b)^*$

$S_2$ is true and at first glance, it looks like its prove must be subtle. But no, it is not difficult to notice that LHS will never have an empty string $\epsilon$, however, the RHS will always have an empty string. This one small difference on the two side of equality will never let them be equal to each other.

Thus, the correct answer is (d) S1 → False, S2 → True

HTH

Comments

I am not able to notice how LHS will never have an empty string ϵ, however, the RHS will always have an empty string?

---

LHS will always contain epsilon and RHS will always contain ø.

Correct me if am wrong.