Chapter 1
Chapter 8
PROPERTIES OF CONTEXT-FREE LANGUAGES
Learning Objectives
At the conclusion of the chapter, the student will be able to:
Apply the pumping lemma to show that a language is not context-free
State the closure properties applicable to context-free languages
Prove that context-free languages are closed under union, concatenation, and star-closure
Prove that context-free languages are not closed under either intersection or complementation
Describe a membership algorithm for context-free languages
Describe an algorithm to determine if a context-free language is empty
Describe an algorithm to determine if a context-free language is infinite
A Pumping Lemma for Context-Free Languages
Theorem 8.1: Given an infinite context-free language L, every sufficiently long string w in L can be broken into four parts uvxyz such that
|vy| ≥ 1
|vxy| m (where m is an arbitrary integer |w|)
An arbitrary, but equal number of repetitions of v and y yields another string in L
The “pumped” string consists of two separate parts (v and y) and can occur anywhere in the string
The pumping lemma can be used to show that, by contradiction, a certain language is not context-free
An Illustration of the Pumping Lemma for Context-Free Languages
As shown in Figure 8.1, the pumping lemma for context-free languages can be illustrated by sketching a general derivation tree that shows a decomposition of the string into the required components
Closure Properties for Context-Free Languages
Theorem 8.3 states that if L1 and L2 are context-free languages, so are the languages that result from the following operations:
L1 L2
L1 L2
L1*
In other words, the family of regular languages is closed under union, intersection, and star-closure.
To prove these properties, we assume the existence of two context-free grammars G1 and G2 that generate the respective languages
Proof of Closure under Union
Assume that L1 and L2 are generated by the context-free grammars G1 = (V1, T1, S1, P1) and G2 = (V2, T2, S2, P2)
Without loss of generality, assume that the sets V1 and V2 are disjoint
Create a new variable S3 which is not in V1 V2
Construct a new grammar G3 = (V3, T3, S3, P3) so that
V3 = V1 V2 { S3 }
T3 = T1 T2
P3 = P1 P2
Add to P3 a production that allows the new start symbol to derive either of the start symbols for L1 and L2
S3 S1 | S2
Clearly, G3 is context-free and generates the union of L1 and L2 , thus completing the proof
Proof of Closure under Concatenation
Assume that L1 and L2 are generated by the context-free grammars G1 = (V1, T1, S1, P1) and G2 = (V2, T2, S2, P2)
Without loss of generality, assume that the sets V1 and V2 are disjoint
Create a new variable S4 which is not in V1 V2
Construct a new grammar G4 = (V4, T4, S4, P4) so that
V4 = V1 V2 { S4 }
T4 = T1 T2
P4 = P1 P2
Add to P4 a production that allows the new start symbol to derive the concatenation of the start symbols for L1 and L2
S4 S1S2
Clearly, G4 is context-free and generates the concatenation of L1 and L2 , thus completing the proof
Proof of Closure under Star-Closure
Assume that L1 is generated by the context-free grammars G1 = (V1, T1, S1, P1)
Create a new variable S5 which is not in V1
Construct a new grammar G5 = (V5, T5, S5, P5) so that
V5 = V1 { S5 }
T5 = T1
P5 = P1
Add to P5 a production that allows the new start symbol S5 to derive the repetition of the start symbol for L1 any number of times
S5 S1S5 |
Clearly, G5 is context-free and generates the star-closure of L1, thus completing the proof
No Closure under Intersection
Unlike regular languages, the intersection of two context-free languages L1 and L2 does not necessarily produce a context-free language
As a counterexample, consider the context-free languages
L1 = { anbncm: n ≥ 0, m ≥ 0 }
L2 = { anbmcm: n ≥ 0, m ≥ 0 }
However, the intersection L1 and L2 is the language
L3 = { anbncn: n ≥ 0 }
L3 can be shown not be context-free by applying the pumping lemma for context-free languages
No Closure under Complementation
The complement of a context-free language L1 does not necessarily produce a context-free language
The proof is by contradiction: given two context-free languages L1 and L2, assume that their complements are also context-free
By Theorem 8.3, the union of the complements must also produce a context-free language L3
Using our assumption, the complement of L3 is also context-free
However, using the set identity below, we conclude that the complement of L3 is the intersection of L1 and L2, which has been shown not to be context-free, thus contradicting our assumption.
Elementary Questions about Context-Free Languages
Given a context-free language L and an arbitrary string w, is there an algorithm to determine whether or not w is in L?
Given a context-free language L, is there an algorithm to determine if L is empty?
Given a context-free language L, is there an algorithm to determine if L is infinite?
Given two context-free grammars G1 and G2, is there an algorithm to determine if L(G1) = L(G2)?
A Membership Algorithm for Context-Free Languages
The combination of Theorems 5.2 and 6.5 confirms the existence of a membership algorithm for context-free languages
By Theorem 5.2, exhaustive parsing is guaranteed to give the correct result for any context-free grammar that contains neither -productions nor unit-productions
By Theorem 6.5, such a grammar can always be produced if the language does not include
Alternatively, a npda to accept the language can be constructed as established by Theorem 7.1
Determining Whether a Context-Free Language is Empty
Theorem 8.6 confirms the existence of an algorithm to determine if a context-free language L(G) is empty
For simplicity, assume that is not in L(G)
Apply the algorithm for removing useless symbols and productions
If the start symbol is found to be useless, then L(G) is empty; otherwise, L(G) contains at least one string
Determining Whether a Context-Free Language is Infinite
Theorem 8.7 confirms the existence of an algorithm to determine if a context-free language L(G) is infinite
Apply the algorithms for removing -productions, unit-productions, and useless productions
If G has a variable A for which there is a derivation that allows A to produce a sentential form xAy, then L(G) is infinite
Otherwise, L(G) is finite
Can be implemented by building a dependency graph which contains an edge from A to B for every rule of the form A xBy
Determining Whether Two Context-Free Languages are Equal
Given two context-free grammars G1 and G2, is there an algorithm to determine if L(G1) = L(G2)?
If the languages are finite, the answer can be found by performing a string-by-string comparison
However, for general context-free languages, no algorithm exists to determine equality
/docProps/thumbnail.jpeg