Stack Overflow
Stack Overflow

Questions tagged [pumping-lemma]

A lemma mostly used to prove that a language is not regular/context-free.

From wikipedia,

In the theory of formal languages in computability theory, a pumping lemma or pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of times, with the resulting string remaining in that language. The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.

128 questions
87
votes
9 answers

What is the Pumping Lemma in Layman's terms?

I saw this question, and was curious as to what the pumping lemma was (Wikipedia didn't help much). I understand that it's basically a theoretical proof that must be true in order for a language to be in a certain class, but beyond that I don't…
shsteimer
  • 28,436
  • 30
  • 79
  • 95
19
votes
2 answers

What exactly is the 'pumping length' in the Pumping lemma?

I'm trying to understand what is this 'magical' number 'n' that is used in every application of the Pumping lemma. After hours of research on the subject, I came to the following website: http://elvis.rowan.edu/~nlt/TheoryNotes/PumpingLemma.pdf It…
Ivan Prodanov
  • 34,634
  • 78
  • 176
  • 248
14
votes
4 answers

To make sure: Pumping lemma for infinite regular languages only?

So this is not about the pumping lemma and how it works, it's about a pre-condition. Everywhere in the net you can read, that regular languages must pass the pumping lemma, but noweher anybody talks about finite languages, which actually are a part…
Lars Knickrehm
  • 739
  • 4
  • 14
8
votes
3 answers

Pumping Lemma with Context Free Languages

I have the language {a^i b^j c^k | i,j,k>=0 & i>j & j>k} I began by assuming some m is picked for me, such that a string z = a^m b^(m-1) c^(m-2) Then the string is split up into (z =) uvwxy so that vx are not empty and #(vwx)<=m Then when I get…
Alex
  • 5,364
  • 9
  • 54
  • 69
7
votes
2 answers

Pumping lemma for regular language

I have a little confusion in checking whether the given language is regular or not using pumping lemma. Suppose we have to check whether: L. The language accepting even number of 0's in regular or not? We know that it is regular because we can…
greenfxpips.com
  • 200
  • 1
  • 3
  • 12
7
votes
3 answers

Why L={wxw^R| w, x belongs to {a,b}^+ } is a regular language

Using pumping lemma, we can easily prove that the language L1 = {WcW^R|W ∈ {a,b}*} is not a regular language. (the alphabet is {a,b,c}; W^R represents the reverse string W) However, If we replace character c with "x"(x ∈ {a,b}+), say, L2 = {WxW^R|…
henry
  • 185
  • 2
  • 2
  • 13
7
votes
2 answers

Using Ogden’s Lemma versus regular Pumping Lemma for Context-Free Grammars

I'm learning the difference between the lemmata in the question. Every reference I can find uses the example: {(a^i)(b^j)(c^k)(d^l) : i = 0 or j = k = l} to show the difference between the two. I can find an example using the regular lemma to…
XML Slayer
  • 1,530
  • 14
  • 31
6
votes
3 answers

generalizing the pumping lemma for UNIX-style regular expressions

Most UNIX regular expressions have, besides the usual **,+,?* operators a backslash operator where \1,\2,... match whatever's in the last parentheses, so for example *L=(a*)b\1* matches the (non regular) language *a^n b a^n*. On one hand, this seems…
Avi
  • 61
  • 1
5
votes
1 answer

Pumping lemma (Regular language)

I need some help with a pumping lemma problem. L = { {a,b,c}* | #a(L) < #b(L) < #c(L) } This is what I got so far: y = uvw is the string from the pumping lemma. I let y = abbc^n, n is the length from the pumping lemma. y is in L because the number…
mrjasmin
  • 1,230
  • 6
  • 21
  • 37
4
votes
3 answers

Pumping lemma for context-sensitive language?

i have googled on pumping lemma for context sensitive, and it seems to only produce results for context-free language. Pumping lemma only allows to prove a language is context free only? and not context sensitive? Any idea how?
user1004413
  • 2,509
  • 6
  • 23
  • 33
4
votes
1 answer

Minimum pumping length for a regular language

How to calculate minimum pumping length of a regular language. For example if i have 0001* then minimum pumping length for this should be 4 ,that is 000 could not be pumped . Why it is so?
vaishali jhalani
  • 91
  • 1
  • 9
3
votes
1 answer

Show that L ={ ww^R : w ∈ Σ*} is not regular by using Pumping Lemma

If I let string w be a^mb^m then we know that y will consists of only a's because of the rule |xy| <= m. And if I set i=0, then ww^R will have fewer a's on the left side than on the right side. Thus, it proves that this language is not…
Mint.K
  • 849
  • 1
  • 11
  • 27
3
votes
1 answer

Did I apply pumping lemma correctly?

L = { w | w in {0,1}* and w has equal number of 0s and 1s } Let n be the number of the pumping lemma. I pick s = 0n 1n and y = 0t where 1 <= t <= n. Which gives xyz = 0(n-t) 0t 1n= 0n 1n which is in L. But xz = 0(n-t) 1n is not in L.…
Ivan Prodanov
  • 34,634
  • 78
  • 176
  • 248
3
votes
2 answers

Can someone help me with this proof using the pumping lemma?

I just started reading about the pumping lemma and know how to perform a few proofs, mostly by contradiction. It is only this particular question which I don't seem to find an answer for. I have no idea on how to begin. I can assume that there has…
n00b1990
  • 1,189
  • 5
  • 17
  • 25
3
votes
2 answers

Pumping lemma for CFLs

My question is: Let L = { x in {a,b}* | x has an equal number of a's and b's} I know this is a context free language because I can create a grammar for it (e is epsilon): S -> aX | bY | e X -> bS | aXX Y -> aS | bYY You can also prove it is…
Neal
  • 6,722
  • 4
  • 38
  • 31
1
2 3
…
8 9