Correct application of the CFL Pumping Lemma

I came across this question about showing that the language $ L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$ is context-free but not linear in the book by Peter Linz. That is easily doable by the separate pumping lemma for linear languages (as given in Linz’s book), but my question is different.

Evidently this is a CFL, and a pushdown automaton can be constructed for it. But if I apply the pumping lemma for CFLs, I find that I’m able to pump strings that don’t belong to the language, which would mean that the language is not a CFL. Clearly I’m doing something wrong.

Going by the "game-like" format given in Linz, say you pick $ w = a^mb^mc^{2m}$ , $ |w| \ge m$ . The adversary can choose a number of decompositions $ w = uvxyz$ , they can look like -:

  • $ v = a^k, y = a^l$ : The case where $ |vxy|$ is contained within the $ a$ ‘s of the string. Pump $ i = 0$ , and then $ w_0 = a^{m – (k + l)}b^mc^{2m}$ cannot be in the language since the equality no longer holds.
  • $ v = a^k, y = b^l$ : The case where $ v$ is in the $ a$ section, $ x$ spans across the $ a$ ‘s and $ b$ ‘s, and $ y$ is in the $ b$ section. Again, pump $ i = 0$ . $ w_0 = a^{m – k}b^{m – l}c^{2m}$ cannot be in the language.

There are more cases like these. Where am I going wrong in the application of the CFL PL?

Use of pumping lemma for not regular languages. (Proof Verification)

$ L=\{w \in \{0,1,a\}^* | \#_0(w) = \#_1(w) \}$

We show that L is not regular by pumping lemma.

We choose w=$ 0^p 1^p a$

|w| = 2p+1

Now |xy| has to be $ \leq p$

So x and y could only contain zeros. And $ z=1^p a$

$ xy^iz= 0^p 1^p a$

Now let i = 0

$ xy^0z=0^{p-|y|} 1^p a$

Now hence $ p-|y| \neq p$ this choice of i would lead to a word that is not in L. So we can not pump y and stay in the language.

So L is not regular.

I’m trying to learn the usage of the pumping lemma. Is my proof correct?

Any suggestions are welcome. Thanks!

Why is this language *not* pumpable? (language = arbitrary word followed by exact same arbitrary word)(pumping lemma for context-free-languages)

1 language = arbitrary word followed by exact same arbitrary word = u * u (with u being out of non-empty words of alphabet {0, 1} )
(sorry for the formatting, see screenshot-link for conventional/clear expression)

The purpose is to prove that the given language is not a context-free-language (using the pumping lemma).

So i thought that this language should definitely be pumpable, since you can choose x and z as corresponding parts in one of the u/"halves". So if word to be pumped is "0101" then you choose e.g. x=1 (0101) and z=1 (0101) and the remaining parts that stay static are assigned with u=0 (0101), y=0(0101), and v=empty.
If pumped zero-times/i=0 word reads: 00
i=1: 0101
i=2: 011011
i=3: 01110111
(and so on)

(For more complicated words you would need to use all three (u, y, v), but the basic principle would still be that x and z are assigned corresponding parts of the word and u,y,v would be assigned the remainder. (This doesn’t work for the extremely small words 00,01,10,11 that would become empty when zero-pumped, but as long as the exceptions are finite / of finite/fixed number this isn’t a problem AFAIU.)
Clearly this is wrong, but can anybody explain how/why?

Difficulty in understand the proof of the lemma : “Matroids exhibit the optimal-substructure property”

I was going through the text "Introduction to Algorithms" by Cormen et. al. where I came across a lemma in which I could not understand a vital step in the proof. Before going into the lemma I give a brief description of the possible prerequisites for the lemma.


Let $ M=(S,\ell)$ be a matroid where $ S$ is the ground set and $ \ell$ is the family of subsets of $ S$ called the independent subsets of $ S$ .

Let us have an algorithm which finds an optimal subset of $ M$ using greedy method as:

$ GREEDY(M,W):$

$ 1\quad A\leftarrow\phi$

$ 2\quad \text{sort $ S[M]$ into monotonically decreasing order by weight $ w$ }$

$ 3\quad \text{for each $ x\in S[M]$ , taken in monotonically decreasing order by weight $ w(x)$ }$

$ 4\quad\quad \text{do if $ A\cup\{x\} \in \ell[M]$ }$

$ 5\quad\quad\quad\text{then $ A\leftarrow A\cup \{x\}$ }$

$ 6\quad \text{return $ A$ }$


I was having a problem in understanding a step in the proof of the lemma below.

Lemma: (Matroids exhibit the optimal-substructure property)

Let $ x$ be the first element of $ S$ chosen by $ GREEDY$ for the weighted matroid $ M = (S, \ell)$ . The remaining problem of finding a maximum-weight independent subset containing $ x$ reduces to finding a maximum-weight independent subset of the weighted matroid $ M’ = (S’, \ell’)$ , where

$ S’ = \{y\in S:\{x,y\}\in \ell\}$ ,

$ \ell’ = \{В \subseteq S – \{x\} : В \cup \{x\} \in \ell\}$ ,

and the weight function for $ M’$ is the weight function for $ M$ , restricted to $ S’$ . (We call $ M’$ the contraction of $ M$ by the element $ x$ .)

Proof:

  1. If $ A$ is any maximum-weight independent subset of $ M$ containing $ x$ , then $ A’ = A — \{x\}$ is an independent subset of $ M’$ .

  2. Conversely, any independent subsubset $ A’$ of $ M’$ yields an independent subset $ A = A’\cup\{x\}$ of $ M$ .

  3. We have in both cases $ w(A) = w(A’) + w(x)$ .

  4. Since we have in both cases that $ w(A) = w(A’) + w(x)$ , a maximum-weight solution in $ M$ containing $ x$ yields a maximum-weight solution in $ M’$ , and vice versa.


I could understand $ (1),(2),(3)$ . But I could not get how the line $ (4)$ was arrived in the proof from $ (1),(2),(3)$ . especially the part in bold-italics. Could anyone please make it clear to me.

validation of a pumping lemma proof for regular languages

i have the following regular expression:

image of the regular expression

of course i could think of a world like w=a^(m+2)b^(m+2)c^(2m+3) and continue with the proof BUT i was just wondering, because L is made up of a union of two expressions, is it valid to split L into L1=a^(i)b^(j)c^(2j-1)| i<=j & i,j>0 L2=a^(i)b^(j)c^(2j-1)| i>=2j-1 & i,j>0

show for each L1 and L2 that the pummping lemma does not work on them (so for l1 i just show that for lets say each k i is not smaller or equal to j, and for l2 i show that i is not always bigger or equal to 2j-1 for each k)

by that i show that l1 and l2 are not regular which means that the union of the two will also be not regular.. is this corrent?

thank you.

Pumping Lemma for CFL – $ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $

I was making exercices about the Pumping Lemma for CFL, and I stumbled up on this language:

$ $ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $ $

I quickly made a CFG that represents that language (or so I believe):

$ $ S \to 0S1 \hspace{0.2cm} | \hspace{0.2cm} A \ A \to 1A0 \hspace{0.2cm} | \hspace{0.2cm} \epsilon $ $

The problem is that I began to think if the Pumping Lemma would hold (it should since I have a CFG for the Language, so it must be a CFL).

(Having the Pumping Lemma in mind) I chose a word, w = $ 0^{n}1^{n}0^{n}1^{n} $ . I immediately stopped because this word will not pass the Pumping Lemma (it can be used to demonstrate that $ \{ ww \hspace{0.2cm}| \hspace{0.2cm} w \in \{0,1\}^{*}\}$ , the language of duplicated words, is not a CFL, I have done it before)

Now I’m stuck with a Pumping Lemma that fails, and a CFG that produces the language and don’t now what to do. I tried to come up with a word that the grammar couldn’t produce and failed, I tried to invalidate the PL but failed (there are no restrictions that tells that the word cannot have all segments of the same size, so $ w$ is in the language).

As far as I know If the PL holds, the language doesn’t have to be a CFL, but if it fails is absolutely unquestionable that the Language is not a CFL.

What I’m I missing?