Pumping lemma for CFG Flashcards
(16 cards)
What is the goal of the pumping lemma for CFLs?
To prove that certain languages are not context-free.
What is the pumping lemma for context-free languages?
If L is a CFL, then there exists n > 0 such that any w ∈ L with |w| ≥ n can be split as w = uvxyz, where |vxy| ≤ n, v ≠ ε or y ≠ ε, and uvⁱx yⁱz ∈ L for all i ≥ 0.
What conditions must the decomposition uvxyz satisfy in the CFL pumping lemma?
- v ≠ ε or y ≠ ε; 2. |vxy| ≤ n; 3. uvⁱ x yⁱ z ∈ L for all i ≥ 0.
What is the intuition behind the pumping lemma for CFLs?
In long enough parse trees, some non-terminal must repeat, creating a subtree that can be pumped.
What is the strategy for using the CFL pumping lemma to prove non-context-freeness?
Assume L is a CFL, pick a long enough word, show all valid decompositions violate the pumping conditions, and conclude a contradiction.
What language is used as the canonical example of a non-context-free language?
L = { aⁿbⁿcⁿ | n ≥ 0 }
Why can’t L = { aⁿbⁿcⁿ } be generated by a CFG?
CFGs can match two counts (like aⁿbⁿ) but not three simultaneously.
In the CFL pumping lemma
what does the constraint |vxy| ≤ n ensure?
What happens if you pump v and y in aⁿbⁿcⁿ?
You disturb the equal balance of a’s, b’s, or c’s, creating a string not in the language.
Why is the language aⁿbⁿcⁿ not context-free?
Because no decomposition uvxyz satisfies the CFL pumping lemma without breaking the required equal counts.
Are context-free languages closed under intersection?
No, the intersection of two CFLs may not be a CFL.
Give an example showing CFLs are not closed under intersection.
L1 = { aⁿbⁿcᵏ }, L2 = { aⁿbᵏcᵏ }; L1 ∩ L2 = { aⁿbⁿcⁿ } which is not context-free.
Are context-free languages closed under complement?
No — if they were, they would also be closed under intersection (which they are not).
What is the general consequence of CFLs not being closed under complement?
You can’t assume the complement of a CFL is context-free, which affects constructions involving set operations.
Which operations are context-free languages closed under?
Union, concatenation, and Kleene star.
Which operations are context-free languages not closed under?
Intersection and complement.
