CS 3156 Section C, Fall 1998
Programming Assignment #2

Write a program that takes a grammar G in Chomsky normal form and a string tex2html_wrap_inline68 as input, and tells whether or not w is in L(G). The input grammar is presented in the format described in the first programming assignment. There is an extra line specifying the string w, as in the following example:

TERMINALS: a b
VARIABLES: S A B C
START: S
S -> AB
S -> BC
A -> BA
A -> a
B -> CC
B -> b
C -> AB
C -> a
STRING: abab

The following observation gives the key of the algorithm: tex2html_wrap_inline76 iff there are two variables B and C (not necesarily distinct) and a number k, tex2html_wrap_inline84 , such that:

  1. the rule tex2html_wrap_inline86 is in G;
  2. tex2html_wrap_inline90 ; and
  3. tex2html_wrap_inline92 .
By repeatedly applying this observation, we see that the question whether tex2html_wrap_inline94 is reduced to answering smaller questions of the type ``is there a derivation from variable A to tex2html_wrap_inline98 in G?''

An efficient way of organizing the computation is the following. For each tex2html_wrap_inline102 , let tex2html_wrap_inline104 denote the set of variables that can generate the string tex2html_wrap_inline98 , i.e.,

displaymath64

(Note that, since tex2html_wrap_inline108 tex2html_wrap_inline110 , w is generated by G if and only if tex2html_wrap_inline116 .) With this notation, the sets tex2html_wrap_inline104 can be computed as follows:

  1. For each tex2html_wrap_inline120 , let tex2html_wrap_inline122 contain all variables A for which tex2html_wrap_inline126 .
  2. For each tex2html_wrap_inline128
    For each tex2html_wrap_inline130
    tex2html_wrap_inline132
    For each tex2html_wrap_inline134 , add to tex2html_wrap_inline136 every A with the property that there exists tex2html_wrap_inline140 and tex2html_wrap_inline142 such that tex2html_wrap_i nline86 is a production of G.