732 views
0 votes
0 votes
1.  If a grammar  is regular then it should satisfy pumping lemma for regular  grammar

2.  But it may possible that the non regular grammar also satisfy pumping lemma.

this statement 2 is true or false .

plz describe.???

4 Answers

1 votes
1 votes
If any language does not satisfy pumping lemma then definitely that language is not regular or CFL whatever that pumping lemma is for. But if any language is satisfying pumping lemma then it never means that language is regular or CFL. It may or maynot be regular.
0 votes
0 votes

If a grammar  is regular then it should satisfy pumping lemma for regular  grammar

Pumping lemma is a concept for LANGUAGES, Not for Grammars. So, If you meant "If a language  is regular then it should satisfy pumping lemma for regular  languages" ... Then It is True.

All the Regular languages satisfy Pumping lemma for Regular languages. But it is One way only i.e. Some Non-regular languages may also satisfy Pumping lemma for Regular languages. 

for e.g. : 

1. $L = \left \{ a^*b^*\, \right \}$ :  is Regular and All the Regular languages do satisfy Pumping lemma for Regular languages.

2. $L = \left \{ w\,\,\,|\,\,w\in \left \{ a,b \right \}^*, n_a(w) = n_b(w) \right \}$ : is Non-regular and Does not satisfy pumping lemma for regular languages. Because whatever Pumping length "P" is taken, There will always be strings which won't be pumped.

3. $L = \left \{ a^mb^nc^n\,\,|\,\,m,n\geq1 \right \}\cup \left \{ b,c \right \}^*$ :  

is Non-regular But Yet it satisfies the Pumping lemma for Regular languages.  Let's rewrite $L$ as

$L = L_1 \cup L_2$ where $L_1 = \left \{ a^mb^nc^n\,\,|\,\,m,n\geq1 \right \}$ and $L_2 = \left \{ b,c \right \}^*$

The language $L$ can be pumped. Since $L_2$ is itself a Regular language, So, Any word from $L_2$ can be pumped arbitrarily and the result is always in $L_2$. Now, See, Any word from $L_1$ can be pumped to any  power by choosing a single "$a$" as the pumped part. Usually the result of pumping is in $L_1$, with the exception of words that only contain a single "a" being pumped to the $0^{th}$ power. But if we pump such a word to the $0^{th}$ power, we erase the only "a" and thus we obtain a word from $L_2$
(That very last observation is the whole reason behind $L_2$ being "added" to $L_1$ -- it is there to complete this technical detail.)


$\color{Red}{\text{Understand Complete Pumping Lemma, Crystal Clear:}}$

Here is Complete Pumping Lemma Lecture: https://youtu.be/8cdPjuYbIrU 

This Pumping Lemma lecture contains EVERYTHING about Pumping Lemma of Regular Languages, i.e. Proof, Examples, Variations, GATE PYQs, Finding minimum pumping length etc. Watch this lecture for Complete, Correct & Clear Understanding.

edited by
0 votes
0 votes

Pumping lemma is a negative test. 

If a language is regular then it strictly follow the pumping lemma.

But we can't say if the language follow the pumping lemma then it is regular.

Related questions

0 votes
0 votes
1 answer
1
srestha asked Apr 19, 2019
651 views
How by Pumping Lemma we can prove that“context free grammar generate an infinite number of strings”and here what could be pumping length ?
0 votes
0 votes
0 answers
3
jg662 asked Feb 22
67 views
Use the Pumping Lemma to show that the following languages over Σ={�,�}Σ={a,b} are not regular. In each case, carefully describe the string that will be pumped and ...