CS计算机代考程序代写 algorithm Chapter 1

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