COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
given grammar is regular
|
|
|
given grammar is not regular
|
|
|
whether two given regular expressions are equivalent or not
|
|
|
None of these
|
Detailed explanation-1: -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. It should never be used to show a language is regular.
Detailed explanation-2: -The pumping lemma is often used to prove that a particular language is non-regular: a proof by contradiction may consist of exhibiting a string (of the required length) in the language that lacks the property outlined in the pumping lemma.
Detailed explanation-3: -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.
Detailed explanation-4: -To identify whether a language is regular or not, is based on Pigeon Hole Principle. This is generally called as the Pumping Lemma.