The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
58 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 in Theory of Computation by (133 points) | 58 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 (19.4k points)
0
thank you sir
0
If a language is not satisfy pumping lemma .then i can say language is non regular???
0
Yes.
0 votes
STATEMENT 2 IS TRUE.
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)

Related questions

0 votes
0 answers
2
asked 22 hours ago in Theory of Computation by Ajit J (129 points) | 15 views
0 votes
0 answers
4
asked Oct 24 in Theory of Computation by Balaji Jegan Active (3.1k points) | 14 views


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

42,573 questions
48,563 answers
155,432 comments
63,582 users