The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
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.???
asked in Theory of Computation by (131 points) | 47 views

4 Answers

+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)
0 votes

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 (18.2k points)
thank you sir
If a language is not satisfy pumping lemma .then i can say language is non regular???
0 votes
answered by (263 points)
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.

answered by (257 points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,437 questions
46,622 answers
57,005 users