The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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.???

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

this statement 2 is true or false .

plz describe.???

+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.

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.)

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 556
- Exam Queries 551
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,894 questions

52,260 answers

182,168 comments

67,679 users