Final Answer:
i) To prove that C is regular, we can construct a regular expression for it. C can be represented by the regular expression: `1+01+`. This expression matches strings where there is at least one '1' followed by '0' and then at least one '1'. Therefore, C is regular.
ii) To prove that D is not regular, we can use the Pumping Lemma for regular languages. Assume D is regular. Let p be the pumping length given by the Pumping Lemma. Consider the string s = "1^p 0^p 1^p", where "^" denotes exponentiation. According to the Pumping Lemma, we can split s into three parts, xyz, where:
1. |xy| ≤ p
2. |y| > 0
3. For all non-negative integers i, xy^iz ∈ D
Now, if we choose i = 2, the resulting string will be of the form "1^(p + |y|) 0^p 1^p". Since |y| > 0, the number of '1's in the first part exceeds the number of '0's in the second part, violating the condition for D. Thus, D cannot be regular.
Step-by-step explanation:
i) To show that C is regular, we provide a regular expression that generates the language C. The regular expression `1+01+` ensures that there is at least one '1' followed by '0' and then at least one more '1', which matches the definition of C.
ii) To prove that D is not regular, we employ the Pumping Lemma, a technique used to show the non-regularity of languages.
We assume D is regular and then use the Pumping Lemma to derive a contradiction. By considering the string "1^p 0^p 1^p," where '^' indicates exponentiation, we show that it cannot satisfy the conditions of the Pumping Lemma, indicating that D is not regular.
This demonstrates the non-regularity of D.