COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
Proof by contradiction
|
|
|
Direct proof
|
|
|
Proof by induction
|
|
|
None of the mentioned
|
Detailed explanation-1: -Which kind of proof is used to prove the regularity of a language? Explanation: We use the method of proof by contradiction in pumping lemma to prove that a language is regular or not.
Detailed explanation-2: -If L is a regular language, then there is an integer n > 0 with the property that: (*) for any string x ∈ L where |x| ≥ n, there are strings u, v, w such that (i) x = uvw, (ii) v = ǫ, (iii) |uv| ≤ n, (iv) uvkw ∈ L for all k ∈ N. To prove that a language L is not regular, we use proof by contradiction.
Detailed explanation-3: -The Myphill Nerode theorem can be used to show a language L is regular by proving that the number of equivalence classes of RL(relation) is finite.
Detailed explanation-4: -The pumping lemma is a property of a regular language. It is used to prove the non-regularity of certain languages. Regular languages always satisfy the pumping lemma. However, if the pumping lemma is satisfied, the language does not need to be regular.
Detailed explanation-5: -The pumping lemma is often used to prove that a particular language is non-regular. Pumping lemma for regular language is generally used for proving a given grammar is not regular. Hence the correct answer is a given grammar is not regular. Pumping Lemma is to be applied to show that certain languages are not regular.