Closure Properties of CFL's - Substitution Proof
Closure Properties of CFL's - Substitution Proof
Closure Properties of CFL's - Substitution Proof
3
There is an O(n3 ) algorithm (n = length
of w) that uses a \dynamic programming"
technique.
✦ Called Cocke-Younger-Kasami (CYK)
algorithm.
Start with a CNF grammar for L.
Build a two-dimensional table:
✦ Row = length of a substring of w.
✦ Column = beginning position of the
substring.
✦ Entry in row i and column j = set of
variables that generate the substring of
w beginning at position j and extending
for i positions.
✦ In reader, these entries are denoted
Xj;i+j ,1, i.e., the subscripts are
the rst and last positions of the
string represented, so the rst row is
X11 ; X22; : : :; Xnn, the second row is
X12 ; X23; : : :; Xn,1;n, and so on.
Basis : (row 1) Xii = the set of variables A such
that A ! a is a production, and a is the symbol at
position i of w.
Induction : Assume the rows for substrings of
length up to m , 1 have been computed, and
compute the row for substrings of length m.
We can derive ai ai+1 aj from A if there is a
production A ! BC, B derives any prex of
ai ai+1 aj , and C derives the rest.
Thus, we must ask if there is any value of k
such that
✦ i k < j.
✦ B is in Xik .
✦ C is in Xk+1;j .
Example
In class, we'll work the table for the grammar:
S ! AS j SB j AB
A!a
B!b
and the string aabb.