starting position ⇒ 
1  2  3  4  5 
5  S,A,C  
4  ∅  S,A,C  
3  ∅  B  B  
2  S,A  B  S,C  S,A  
1  B  A,C  A,C  B  A,C 
length ⇑  b  a  a  b  a 
Basic Contextfree Language closure properties
CFL's satisfy the following closure properties: If L_{1} and L_{2} are CFLs then so is L_{1} ∪ L_{2}.
 If L_{1} and L_{2} are CFLs then so is L_{1} · L_{2}.
 If L is a CFL then so is the Kleenestar: L^{*}.
(V_{1}  Σ_{1}) ∩ (V_{2}  Σ_{2}) = ∅Choose a "new" S, i.e., S ∉ V_{1} ∪ V_{2}. For union and concatenation, the new grammar is
G′=(V′,Σ′,R′,S)where
V′ = V_{1} ∪ V_{2} ∪ {S}For union,
R′ = R_{1} ∪ R_{2} ∪ {S → S_{1}, S → S_{2}}For concatenation:
R′ = R_{1} ∪ R_{2} ∪ {S → S_{1}S_{2}}
For Kleene^{*}, take any grammar: G_{}=(V,Σ,R,S). Choose a "new" start symbol S′ ∉ V. The grammar for L(G)^{*} is (V′,Σ,R′,S′) with
V′ = V ∪ {S′} R′ = R ∪ {S′ ⇾ S′S, S ⇾ ε}
Intersection closure properties
In a subsequent section we will see a pumping lemma equivalent for CFLs. It turns out that this language is not contextfree:{ a^{n}b^{n}c^{n} : n ≥ 0 }However we can construct it as the intersection of two contextfree languages. Thus CFLs are not closed under intersection. Consequently they cannot be closed under complementation because if they were, then using DeMorgan's Laws plus closure under union, we would have closure under intersection. There is a partial result which is true: the intersection of a CFL and a regular language is a CFL. In order to prove this we need the alternative machine model for CFLs called PDAs. That is coming up next.
Language Algorithms
Language algorithms are usually framed as socalled decision problems: given a language or languages or Let's consider the situation for regular languages. Suppose we have regular languages L, L_{1} and L_{2} over Σ. All of the following questions are decidable in the sense that there is an algorithmic way to obtain the answer: is ε ∈ L?
 is w ∈ L, for a given w ∈ Σ^{*}?
 is L = ∅?
 is L = Σ^{*}?
 is L_{1} ⊆ L_{2}?
 is L_{1} = L_{2}?
 is L_{1} ∩ L_{2} = ∅?
 is ε ∈ L?
 is w ∈ L, for a given w ∈ Σ^{*}?
 is L = ∅?
CFLs not closed under complementation
It is important to understand what makes it work for regular languages, but not for contextfree languages. The crux of the problem is that regular languages are closed under complementation but contextfree languages are not.Eliminate useless symbols
A symbol X (terminal or nonterminal) is useful if it appears in the derivation from the start symbol to a terminal string, i.e.,S ⇒* αXβ ⇒* w ∈ Σ*A symbol which is not useful is useless. We can ignore it and all the rules it appears in. Useful means:
 connected from the start
 connected to the end
S → aAB  a B → Bb C → b A → aA is useless even though S ⇒* aAB and A ⇒* a. In fact, the symbols A, B, C and b are all useless; then only useful rule is:
S → a
Step 1: eliminate nonterminals which don't derive anything
We start by algorithmically computing the "end half" of usefulness as follows:OLD = ∅ NEW = { A : A → α ∈ Σ* } while (OLD != NEW) { OLD = NEW; NEW = OLD ∪ { A : A → α ∈ (Σ ∪ OLD)* } }When this terminates, discard all rules which do use nonterminals not in NEW. For example, consider the grammar ({S,A,B,C,a,b,c},{a,b,c},R,S) with R:
S → Aa  aBb A → bAb B → bBb  A  a C → a  cB and C would be added initially. The following step S is added because S → aBb. At this point we would eliminate A, getting the reduced grammar ({S,B,C,a,b,c},{a,b,c},R_{1},S) with R_{1}:
S → aBb B → bBb  a C → a  c
Algorithmic determination whether L(G) is not empty
We can algorithmically determine whether L(G) ≠ ∅ as follows:L(G) ≠ ∅ if and only if S is in the remaining set of nonterminals computed by step 1.
Step 2: eliminate symbols which are not reachable from S
After applying step 1, we have potentially reduced the nonterminals and rule set. If we discover that L(G) = ∅, we do not proceed. Otherwise, we run a similar algorithm, this one going from the start symbol "down":OLD = ∅ NEW = { S } while (OLD != NEW) { OLD = NEW; NEW = OLD ∪ { X ∈ V : A → αXβ, A ∈ OLD } }At this point discard all rules with symbols not in NEW. Here we are trying to compute all symbols, terminals or nonterminals, which appear in a derivation from the start symbol. This leaves us with the final grammar with all useful symbols and useful rules. In our example, the initialization sets NEW = {S}, the next step we get NEW = {S,a,B,b}. The next step using B gives nothing new and so we have the final grammar ({S,B,a,b},{a,b},R_{1},S) with R_{2}:
S → aBb B → bBb  a
Eliminate epsilon productions
Given G=(V,Σ,R,S), assume it is modified so that all symbols are useful. The idea is as follows: decide whether ε ∈ L(G)
 remove all rules of the form A → ε
 if ε ∈ L(G), create a new start symbol S′ and add: S′ → S  ε
Erasable (nullable) nonterminals
The proof is based on the following computation of the set of erasable, or nullable nonterminals:Ε = { A ∈ V  Σ : A ⇒^{*} ε }The computation is this:
OLD = ∅ NEW = { A : A → ε } while ( NEW ≠ OLD ) { OLD = NEW; NEW = OLD ∪ { A : A → α ∈ OLD^{*} } } Ε = NEW;For example, with this grammar (with all useful symbols):
D → ABC C → AB  c Q → Qa  b B → ε  b  abDQ A → ε  aA and B would be added on first pass, C added the next pass and D the third pass.
Algorithmic determination whether ε ∈ L(G)
We can algorithmically determine whether ε ∈ L(G) by computing the set, Ε of erasable nonterminals and checking if S ∈ Ε. Implicit in the computation of erasable symbols is the assumption that all symbols are useful, otherwise we could have A → ε for a useless rule and have incorrectly judged that ε ∈ L(G).Grammar modification
With the above grammar the idea is to eliminate these two rules:A → ε B → εHow should we compensate? For each rule A → α, add new rules gotten by omitting one or more occurrence of the erasable symbols.
Back to Example
In this example, with erasable symbols A, B, C, D, this would mean adding the rules:B → abQ C → A  B D → AB  AC  BC  A  B  CIn our example, ε ∈ L(G), and so we add
S → D  εOur final grammar is this:
S → D  ε D → ABC  AB  AC  BC  A  B  C Q → Qa  b C → AB  c  A  B B → b  abDQ  abQ A → a
The a^{n}b^{n} language
With the grammarS ⇾ aSb  εThe start symbol is nullable. For the rule S ⇾ aSb, make the replacement of S by ε to get the added rule S ⇾ ab. The final grammar is:
S′ ⇾ S  ε S ⇾ aSb  ab
Balanced Parentheses
Let's consider the balanced parentheses grammar:S → SS  (S)  εThe only symbol S is nullable and so the grammar would transform into the following:
S′ → S  ε S → SS  (S)  S  ()Note that the rule S → S cannot possibly add anything to L(G), and so we omit this, getting:
S′ → S  ε S → SS  (S)  ()
Eliminate unit productions
A unit production is one of the formA → BOnce we have eliminated εproductions, we can guarantee that:
A ⇒* B if and only if the derivation consists entirely of unit productions
because otherwise, another symbol appearing in the
derivation could never disappear.
So we can readily determine
by graphical means whether A ⇒* B.
Grammar Modifications
Assume that we have already executed the previous two steps: Remove useless symbols.
 Eliminate εproductions
 Remove all the unit productions.
 For each remaining (nonunit) production B → α, add A → α if A ⇒* B.
 Again, identify and remove useless symbols (step 2 only), because the removal of the unit productions may have caused some nonterminals to be unreachable from S.
S → A  Bb A → C  a B → aBa  b C → aSathen the unit productions are:
S → A A → Cand we obviously also have S ⇒* C, and so, when unit productions are eliminated, we get:
S → Bb  a  aSa A → a  aSa B → aBa  b C → aSaNow both A and C have become useless because they are unreachable from S, and our final modified grammar becomes:
S → Bb  a  aSa B → aBa  b
Balanced Parentheses
For the balanced parentheses, we would technically have to replace the S′ → S production from the εremoved grammar, getting the grammar:S′ → SS  (S)  ()  ε S → SS  (S)  ()
Chomsky Normal Form
According to the textbook, a grammar is in Chomsky Normal Form if the RHS of each production has length exactly 2. Not every textbook is quite this stringent. We'll use a more relaxed version of CNF. A grammar is in CNF if all productions are one of two forms: A → BC, where A, B, C are nonterminals
 A → a, where a is a terminal
 if ε ∈ L, then there is a production S → ε using the start symbol S, such that S never appears on the right hand side of any production.
Theorem: Every grammar has an equivalent grammar in CNF.
Apply all steps up to this point in sequence:
 eliminate useless symbols (and associated productions)
 eliminate εproductions, thereby possibly adding some new productions
 eliminate unitproductions and possibly adding other productions
 eliminate useless symbols (second time)
Therefore, the only productions whose righthand sides have length less than 2 are the terminal productions, i.e., those of the form:
B → σ ∈ Σ
Make productions which are not terminal productions consist only nonterminals
If a production has length ≥ 1, and contains one or more terminal symbols then we can easily replace this production by one with only nonterminals. Simply create a new nonterminal T, create a new productionT → σand replace each occurrence of σ in the righthand side of any production by T. Using our running example, which at this stage is:
S → a  Bb  aSa A → a  aSa B → b  aBaWe make these further modifications:
S → a  BY  XSX A → a  XSX B → b  XBX X → a Y → b
Make the righthandsides have length exactly 2
The final step is to normalize the right hand side of each production which is not a terminal production to have length exactly two. This is very straightforward, simply introduce enough new nonterminals to effect a chaining. For exampleA → XSXbecomes
A → XZ_{1} Z_{1} → SXThe last two steps (especially the last one) are completely artificial. The goal is simply to achieve the normal form result. ■
Example: Convert expression grammar to CNF
Given a simplified version of our expression grammar:E → E + T  T T → T * F  F F → (E)  aAll symbols are useful and there are no εproductions. So start by eliminating unit productions. In particular eliminate
E → T, T → FThe additions are based on the facts that:
E ⇒* T, T ⇒* F, E ⇒* Fand so we get
E → E + T  T * F  (E)  a T → T * F  (E)  a F → (E)  aNow comes the artificial part. Remove the terminals (, ), *, + using these replacements:
P → + M → * L → ( R → )and getting:
E → EPT  TMF  LER  a T → TMF  LER  a F → LER  aNow to make the righthand sides have length 2, introduce these replacements:
E → EX, X → PT E → TY, Y → MF E → LZ, Z → ER T → TY T → LZ F → LZOur final CNF form is this:
E → EX  TY  LZ  a T → TY  LZ  a F → LZ  a X → PT Y → MF Z → ER P → + M → * L → ( R → )
The CockeYoungerKasami (CYK) algorithm
With CNF, you can predict how many steps it will take to derive a string based on its length:length 0: derivable from start symbol only length 1: 1 step from S length 2: 1 + 2 = 3 steps, e.g. S ⇒ AB ⇒ aB ⇒ ab length 3: 2 + 3 = 5 steps: S ⇒ AB ⇒ ABC ⇒^{3} abc ... length n: (n1) + n = 2n  1 steps.Given a grammar G and a string w, we can imagine an algorithm to determine whether w ∈ L(G). We do so by successively deriving all the strings of length w in a systematic manner and then see if w is one of those. However, we can do better than this. The CYK algorithm takes a grammar in Chomsky Normal Form (CNF) and computes the set of all symbols in the grammar which can derive a given string w. After execution of the algorithm we know that w ∈ L if and only if the start symbol S is in this set. This algorithm was the first to provide a polynomial worstcase time, O(n^{3}), for determining whether a given string w ∈ L(G) for a grammar G in CNF. The idea is to take w = σ_{1}...σ_{n} and compute all nonterminals which derive all substrings of w:
w_{i,j} = σ_{i}...σ_{i+j1} = the substring of length j starting at position iThe CYK algorithm computes the following sets of nonterminals:
N_{i,j} = { A : A ⇒* w_{i,j} }In particular, w_{1,n} = w, and so N_{1,n} = { A : A ⇒* w } The algorithm is as follows:
for (i = 1..n) N_{i,1} = { A : A → σ_{i} } for (j = 2..n) // j = substring length for (i = 1..nj+1) // i = starting position for (k = 1..j1) // k = substring split length if A → BC && B ∈ N_{i,k} && C ∈ N_{i+k,jk} N_{i,j} = N_{i,j} ∪ { A }Here is an example. Consider the grammar:
S → AB  BC A → BA  a B → CC  b C → AB  aWe want to compute the nonterminals which derive the string w = baaba, and so, as suggested, compute all nonterminals which derive all substrings of w starting from length 1 up to w. The following table illustrates that the nonterminals S,A,C all derive baaba. In particular, baaba ∈ L(G).

The {S,A} in cell (1,2) is the result of concatenating nonterminals from
positions (1,1) and (2,1): BA, BC
Match these against the righthand sides of productions and add lefthand sides when a match occurs, getting {S,A}. 
The {B} in cell (3,3) is the result of concatenating nonterminals from
positions (3,1) and (4,2): AS, AA, CS, CA positions (3,2) and (5,1): SA, SC, CA, CC
Match these against the righthand sides of productions and add lefthand sides when a match occurs. The only righthand side matches is CC which effects the inclusion of lefthand side {B}. 
The {S,A,C} in cell (2,4) is the result of concatenating nonterminals from
positions (2,1) and (3,3): AB, AC positions (2,2) and (4,2): BS, BA positions (2,3) and (5,1): BA, BC
Match these against the righthand sides of productions and add lefthand sides when a match occurs. The righthand side matches are AB and BA which effect the inclusion of lefthand sides {S,A,C}.