Ask Question
28 October, 22:15

Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection, and complement

+5
Answers (1)
  1. 28 October, 22:27
    0
    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}

    +}.
Know the Answer?
Not Sure About the Answer?
Find an answer to your question 👍 “Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under ...” in 📗 English if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers