Although it is easy to find the exact position of a grammar in the Chomsky hierarchy, it is sometimes much more challenging to find the position of a language in the Chomsky hierarchy. The Bar-Hillel lemma is the first pumping - also called iteration - lemma, which gives properties shared by all context-free languages. Thus, if a language does not satisfy the conditions of the lemma, it is not context-free. This lemma - and its variations - can be used to show that a language is not context-free. On the other hand, languages satisfying the conditions may be not context-free.

**Theorem 17.** **(Bar-Hillel lemma)** *For each context-free language L there exists an
integer n* ≥ 1 *such that each string p* ∈ *L*,
∣*p*∣ ≥ *n can be written in a form p = uvwxy,
where* ∣*vwx*∣ ≤ *n*, ∣*vx*∣ ≥ 1
*and uv ^{i}wx^{i}y* ∈

**Proof.** *Let L*_{1} = *L* \ {λ}.
It is ovious that if language *L*_{1} satisfies the above conditions then language
*L* = *L*_{1} ∪ {λ} also holds the above conditions,
so it is enough to prove the lemma for λ-free context-free languages.

Theorem 16 shows that each λ-free context-free language can be generated by a Chomsky normal form grammar.
Further on let us assume that grammar *G* generating *L*_{1} is in Chomsky normal form.

Let us mark the number of nonterminals in grammar *G* by *k*, and let
*n* = 2* ^{k}*+1. Let

S⇒^{*}uAy⇒^{*}uwyS⇒^{*}uAy⇒^{*}uvAxy⇒^{*}uvwxyS⇒^{*}uAy⇒^{*}uvAxy⇒^{*}uvvAxxy⇒^{*}uvvwxxy⋮

This proves that *uv ^{i}wx^{i}y* ∈

Finally, ∣*vwx*∣ ≤ *n*, because the word *vwx* was derived with a
derivation subtree of height at most *k*+2, - where the last step was
a nonterminal to terminal derivation, - so the length of the word *vwx* is maximum 2* ^{k}*
which is less than

QED.

**Example 41.** *The following classical example shows an application of the Bar-Hillel lemma.
We are going to prove that language L* =
{*a ^{j}b^{j}c^{j}*∣

**Example 42.** *Let us consider the language
L* ={*a ^{j}b^{k}c^{j}d^{k}*∣

**Example 43.** *In this example we consider the language
L* = {*wcw*∣*w* ∈
{*a,b*}^{*}}, *and we use the Bar-Hillel lemma to prove that this language is not context-free.
Suppose to the contrary
that the language L is context-free, in this case the word
a ^{n}b^{n}ca^{n}b^{n}
can be written in a form uvwxy such that uv^{i}wx^{i}y* ∈

**Example 44.** *In this example we show that the language L* =
{*a ^{p}*∣