Question

2. (35 pt.) Prove that the following languages are not regular using the pumping lemma.

   1. (15pt.)?={?????? |?,?≥?}

   2. (20 pt.) ? = {? ∈ {?, #}∗ | ? = ??#??# ... #?? ??? ? ≥ ?, ?? ∈ ?∗ ??? ????? ?, ??? ?? ≠?? ???????? ?≠?}
      Hint: choose a string ? ∈ ? that contains ? #’s.

Answer 1

Prove that the following languages are not regular using the pumping lemma.
?={?^??^??^? |?,?≥?}

Solution:-----.
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, xyⁱz ∈ L.
Choose, s = 0^p10^p . 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 = 0^k for some
k > 0. Per (c), we can take i = 0 and the resulting string will still be in L. Thus, xy⁰z should be in L. xy⁰z = xz = 0^(p−k)10^p . 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.