83 views
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.???
asked | 83 views

+1 vote
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.
answered by (31 points)

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

Pumping lemma is 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.)

answered by Boss (22.5k points)
0
thank you sir
0
If a language is not satisfy pumping lemma .then i can say language is non regular???
0
Yes.
STATEMENT 2 IS TRUE.
answered by (263 points)

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.

answered by (445 points)