COMPUTER SCIENCE AND ENGINEERING
THEORY OF COMPUTATION
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
|
|
2
|
|
|
3
|
|
|
4
|
|
|
5
|
Detailed explanation-1: -While applying Pumping lemma over a language, we consider a string w that belong to L and fragment it into parts. Explanation: We select a string w such that w=xyz and |y|>0 and other conditions. However, there exists an integer n such that |w|>=n for any wÎL. 3.
Detailed explanation-2: -Explanation: Pumping lemma is used to prove a language is regular or not. So, option (D) is correct.
Detailed explanation-3: -If A is a regular language, then there is a number p where if s is any string in A of length at least p, then s may be divided into three pieces, s = xyz, satisfying the following conditions: for each i ≥ 0, xyiz ∈ A.
Detailed explanation-4: -There are two Pumping Lemmas (PL), which are defined for Regular Languages and Context-Free Languages.
Detailed explanation-5: -Pumping Lemma is used as a proof for irregularity of a language. Thus, if a language is regular, it always satisfies pumping lemma. If there exists at least one string made from pumping which is not in L, then L is surely not regular. The opposite of this may not always be true.