PadhaikoAll subjects

CFL Closure, Pumping Lemma & Decision Algorithms

Theory of Computation (ENCT 203)

Open in the Padhaiko app

CFL Closure, Pumping Lemma & Decision Algorithms

While context-free languages possess substantially greater expressive power than regular languages, their mathematical properties differ significantly. In particular, context-free languages are closed under union, concatenation, and Kleene star, but fail to be closed under intersection and complementation. To formally prove that a language is non-context-free, we employ the Pumping Lemma for Context-Free Languages. Furthermore, examining the decision algorithms reveals that questions of emptiness, finiteness, and membership are decidable for CFLs, whereas equivalence and ambiguity are provably undecidable.


3.4 Closure Properties of Context-Free Languages

Unlike regular languages, which form a boolean algebra closed under all standard set operations, context-free languages are closed under only a subset of these operations.

Theorem

Closure under Union, Concatenation, and Kleene Star

The family of context-free languages is closed under:

  1. Union ()
  2. Concatenation ()
  3. Kleene Star ()

Proof

Let and be two context-free languages generated by context-free grammars and respectively. Without loss of generality, assume their non-terminal variable sets are disjoint (). Let be a fresh start symbol not in .

  1. Union (): Construct a new grammar where:
    • Any derivation begins with either or . Thus .
  2. Concatenation (): Construct with productions:
    • A derivation proceeds as where and . Hence .
  3. Kleene Star (): Construct where:
    • The rule yields the empty string . The recursive rule generates arbitrary sequences . Hence .
Theorem

Non-Closure under Intersection and Complementation

The family of context-free languages is not closed under:

  1. Intersection ()
  2. Complementation ()

Proof

  1. Non-closure under Intersection (Counterexample): Consider the two languages:

Both languages are context-free:

As proven by the Pumping Lemma, is not context-free. Thus, CFLs are not closed under intersection.

  1. Non-closure under Complementation (Proof by Contradiction): Assume for contradiction that CFLs are closed under complementation. Let be context-free languages. By our assumption, their complements and must also be CFLs. Since CFLs are closed under union, the language is context-free. Applying complementation once more, the language must also be context-free. However, by De Morgan's Law:

This implies that the intersection of any two CFLs is context-free, which directly contradicts the fact that CFLs are not closed under intersection. Hence, CFLs are not closed under complementation.


3.5 Pumping Lemma for Context-Free Languages

Theorem

Pumping Lemma for Context-Free Languages

Let be any context-free language. Then there exists a positive integer constant (the pumping length) depending only on such that for any string with , can be decomposed into five substrings:

satisfying the following three conditions:

  1. (the middle subsegment is bounded in length by )
  2. (the pumpable pieces and are not both empty; at least one has length )
  3. for all integers (pumping and simultaneously preserves membership)

Proof

Let be a CFG in Chomsky Normal Form for with non-terminals. In CNF, every parse tree is a binary tree. A tree of height can yield a string of length at most .

Let . If , any parse tree for must have height at least . By the Pigeonhole Principle, along the longest path from the root to a leaf, there must be at least non-terminal labels. Since there are only distinct non-terminals, at least one non-terminal variable must repeat:

By repeating the derivation cycle times, we obtain for all . Choosing the two lowest repetitions of ensures that the sub-tree rooted at the upper has height , guaranteeing . Since CNF has no unit or -rules, the expansion must generate at least one terminal, ensuring .

Methodology: Adversarial Game for Pumping Lemma

To prove that a language is not context-free:

  1. Assume is context-free. The Pumping Lemma guarantees an unknown pumping constant .
  2. Choose a specific string with , expressed symbolically in terms of .
  3. Analyze all possible decompositions constrained by and .
  4. Find an integer (typically or ) such that .
  5. The contradiction disproves the assumption, establishing that is not context-free.

3.6 Decision Algorithms for Context-Free Languages

Decision algorithms are effective computational procedures that terminate in finite time with a definitive Yes/No answer.

Definition

Decidability of Problems for CFLs

For Context-Free Languages:

  1. Emptiness Problem (Decidable):
    • Question: Is ?
    • Algorithm: Compute the set of generating variables using the dynamic programming mark algorithm. If the start symbol is generating, then ; otherwise .
  2. Finiteness Problem (Decidable):
    • Question: Is finite?
    • Algorithm: Convert to CNF without useless symbols. Construct the directed variable dependency graph ( if or ). If the graph contains a directed cycle reachable from and capable of deriving terminals, is infinite; otherwise is finite. Equivalently, test whether derives any string of length with where is the pumping constant.
  3. Membership Problem (Decidable):
    • Question: Given string and CFG , is ?
    • Algorithm: Convert to CNF. Execute the Cocke-Younger-Kasami (CYK) algorithm, a dynamic programming tabular algorithm running in time. If , then .
  4. Equivalence Problem (Undecidable):
    • Question: Given CFGs and , is ?
    • Status: Undecidable. There is no algorithm that can determine language equivalence for arbitrary context-free grammars (provable by reduction from the Post Correspondence Problem).
  5. Ambiguity Problem (Undecidable):
    • Question: Given a CFG , is ambiguous?
    • Status: Undecidable. It is impossible to algorithmically decide whether an arbitrary CFG possesses ambiguous strings.

Worked Out Examples: Proving Non-Context-Free Languages

Example 1

1

Prove using the Pumping Lemma for CFLs that the language:

is not context-free. [2081 Chaitra, 2074 Ashwin]

Assuming L is Context-Free

Assume for contradiction that is a context-free language. By the Pumping Lemma for CFLs, there exists a pumping constant .

Selecting a Test String

Choose the string . Here, , so . The total length is .

Decomposition Constraints

By the Pumping Lemma, must be partitioned into such that:

  1. for all .

Because , the substring cannot span both halves of the string simultaneously in a balanced manner:

  • Case 1: falls entirely within the first half . Pumping increases the count of symbols in the first half without changing the second half, yielding a string whose two halves cannot match.
  • Case 2: straddles the boundary between the first and second . Then contains at most 's and 's. Pumping increases the number of 's in the first half and 's in the second half, destroying the block structure.
  • Case 3: falls entirely within the second half . Pumping changes the length and composition of the second half while leaving the first half unchanged.
Contradiction via Pumping

In every case, for , the pumped string cannot be factored into two identical halves . Therefore, .

Answer:

The contradiction disproves our assumption. Thus, is not context-free.

Example 2

2

Using the Pumping Lemma for Context-Free Languages, show that:

is not context-free. [2072 Kartik]

Assuming L is Context-Free

Assume for contradiction that is context-free. Let be the pumping constant given by the Pumping Lemma.

Selecting a String

Select the string . The length is .

Analyzing the Substring vxy

The Pumping Lemma dictates that with and . Because , the substring cannot contain all three symbols and simultaneously:

  • Subcase A: contains at most one symbol type (only 's, only 's, or only 's). Then pumping increases the count of that single symbol, while the other two symbol counts remain . The resulting string does not have equal numbers of 's, 's, and 's.
  • Subcase B: contains two symbol types ('s and 's, or 's and 's). Then and together contain at most two distinct symbols. Pumping increases the counts of these two symbols while the third symbol count remains strictly .
Deriving the Contradiction

In all cases, the third symbol's count is unchanged, so:

This contradicts the condition that for all .

Answer:

Therefore, the language is not context-free.

Example 3

3

Show using the Pumping Lemma for CFLs that the language:

is not a context-free language. [2074 Chaitra]

Setup and String Selection

Assume is context-free with pumping constant . Select the string:

with total length .

Evaluating Pumping Partitions

The decomposition requires and :

  • Because , the segment can span at most two consecutive blocks of symbols ('s and 's, or 's and 's). It cannot touch 's and 's at the same time.
  • If and contain only 's and 's, pumping increases the counts of and/or , while the number of 's remains fixed at . The ratio is violated.
  • If and contain only 's and 's, pumping increases and/or , while the count of 's remains fixed at . Again, the ratio is violated.
Conclusion

In all possible placements of and , .

Answer:

Hence, is not context-free.


Exercise Set: CFL Closure, Pumping Lemma & Decisions

Exercise Questions: Closure & Pumping Lemma

Question 1

Show that context-free languages are not closed under intersection and complementation operations, but are closed under concatenation. [2082 Kartik, 2079 Bhadra, 2079 Baishakh]

Proof of Closure under Concatenation: Let and be two context-free languages generated by CFGs and . Without loss of generality, rename variables so that . Define a combined grammar for the concatenation :

  • (where is a new start symbol)

Any derivation from begins with . Because and are disjoint, can only derive strings and can only derive strings . Thus . Conversely, any string in factors into and and is derived by . Hence , proving CFLs are closed under concatenation.

Counterexample Proving Non-Closure under Intersection: Consider two context-free languages over alphabet :

  • (generated by )
  • (generated by )

Both and are context-free. Now consider their intersection:

By the Pumping Lemma for CFLs, is not context-free. Because but , context-free languages are not closed under intersection.

Proof of Non-Closure under Complementation: Assume for contradiction that CFLs were closed under complementation. We know context-free languages are closed under union (via ). By De Morgan's Law for set operations:

If CFLs were closed under complementation:

  1. and would be CFLs (by complementation closure).
  2. would be a CFL (by union closure).
  3. would be a CFL (by complementation closure).

This would force CFLs to be closed under intersection, directly contradicting the counterexample proved above. Therefore, context-free languages are not closed under complementation.

Answer:
  1. Concatenation: Given CFGs with disjoint variables, define . Then , proving closure.
  2. Intersection: and are CFLs, but their intersection is not a CFL.
  3. Complementation: If CFLs were closed under complementation, then by De Morgan's Law would be a CFL, contradicting non-closure under intersection.
Question 2

What are the closure properties of Context-Free Languages? [2082 Baishakh]

Operations Under Which CFLs Are Closed: Context-Free Languages are closed under the following operations:

  1. Union (): Add production .
  2. Concatenation (): Add production .
  3. Kleene Star (): Add production .
  4. Reversal (): Reverse the right-hand side of every production rule ().
  5. Homomorphism (): Replace each terminal in production bodies with string .
  6. Inverse Homomorphism (): Recognizable by constructing a PDA with an input buffer.
  7. Intersection with a Regular Language (): Product construction simulating a PDA and a DFA in parallel (cross-product of states).

Operations Under Which CFLs Are NOT Closed: CFLs fail closure under three fundamental set operations:

  1. Intersection ():
    • Counterexample: and are CFLs, but .
  2. Complementation ():
    • By De Morgan's Law, closure under complementation and union would imply closure under intersection (), which is false.
  3. Set Difference ():
    • Since is regular (and hence a CFL), if difference were closed, then would be context-free, which is false.

Closure Summary Comparison:

OperationRegular LanguagesContext-Free Languages
Union ()ClosedClosed
Concatenation ()ClosedClosed
Kleene Star ()ClosedClosed
Reversal ()ClosedClosed
Homomorphism ()ClosedClosed
Intersection ()ClosedNot Closed
Complementation ()ClosedNot Closed
Set Difference ()ClosedNot Closed
Intersection with Regular ()ClosedClosed
Answer:

Context-Free Languages are closed under union, concatenation, Kleene star, reversal, and homomorphism, as well as intersection with a regular language. However, CFLs are not closed under intersection, complementation, or set difference.

Question 3

State and describe the Pumping Lemma for Context-Free Languages. [2082 Baishakh, 2079 Baishakh]

Formal Statement of the CFL Pumping Lemma: Let be any context-free language. There exists a positive integer constant (the pumping constant, dependent only on ) such that for every string with length , can be partitioned into five substrings:

satisfying all three conditions:

  1. (the middle substring has bounded length).
  2. (at least one of the pumped substrings or is non-empty).
  3. For every integer , the pumped string belongs to :

Theoretical Basis (Parse Tree Repetition):

Because variable generates both and terminal string , the recursive subderivation can be repeated times for any :

  • For : (pumping down).
  • For : (pumping up).

Usage as an Adversarial Proof Technique: The Pumping Lemma cannot be used to prove a language is context-free; it is used as a proof by contradiction to prove a language is not context-free:

  1. Assume is context-free; an adversary selects pumping constant .
  2. We choose a specific string with parameterized by .
  3. The adversary chooses a partition meeting and .
  4. We choose an exponent (commonly or ) and show that for every possible partition chosen by the adversary.
  5. The contradiction disproves the assumption, establishing that is not context-free.
Answer:

For any CFL , there exists a constant such that any string with can be written as with , , and for all . It is used as a proof technique by contradiction to establish that a language is not context-free.

Question 4

Prove that Context-Free Languages are closed under union and concatenation operations. [2078 Kartik]

Grammar Setup and Variable Disjointness: Let and be two context-free languages. By definition, there exist context-free grammars:

such that and . Rename variables if necessary so that . Introduce a new start symbol .

Proof of Closure under Union (): Construct grammar where:

Correctness:

  • If , . In , derivation generates .
  • If , . In , derivation generates .
  • Conversely, any derivation from must begin with or . Because , a derivation starting from can only use rules from , generating a string in ; similarly from generating a string in .

Therefore , proving CFLs are closed under union.

Proof of Closure under Concatenation (): Construct grammar where:

Correctness:

  • For any and , and . In :

Thus .

  • Conversely, any derivation from begins with . Because and are disjoint, productions in cannot rewrite variables in , and vice versa. Hence derives a terminal string and independently derives , yielding .

Therefore , proving CFLs are closed under concatenation.

Answer:

Let be CFGs for with start symbols and disjoint variable sets. For union, add start symbol with rule , generating . For concatenation, add start symbol with rule , generating .

Past exam questions for Theory of Computation

← Simplification of CFG; CNF, GNF & BNFPushdown Automata, CFG↔PDA & Context-Sensitive Grammar →