Answer: Explained
Explanation:
To prove that L is not a regular language, we will use a proof by contradiction. Assume
that L is regular. Then by the Pumping Lemma for Regular Languages, there exists a
pumping length, p for L such that for any string s ∈ L where |s| ≥ p, s = xyz subject
to the following conditions:
(a) |y| > 0
(b) |xy| ≤ p, and
(c) ∀i > 0, xyi
z ∈ L.
Choose s = 0p10p
. Clearly, |s| ≥ p and s ∈ L. By condition (b) above, it follows that
x and y are composed only of zeros. By condition (a), it follows that y = 0k
for some
k > 0. Per (c), we can take i = 0 and the resulting string will still be in L. Thus,
xy0
z should be in L. xy0
z = xz = 0(p−k)10p
. But, this is clearly not in L. This is a
contradiction with the pumping lemma. Therefore our assumption that L is regular is
incorrect, and L is not a regular language.
b. L = {wtw | w, t ∈ {0, 1}
+}.
