The CYK algorithm can be described as bottom-up because it starts with the word and works up to the nonterminals. There is another method for deciding membership that is top-down in nature. Create a table with one column for each nonterminal that appears in the grammar and n rows, where n is the length of the subject word. The entries for cell (i,j) are those words of length i that can be derived from the nonterminal, N_j' at the head of the column. The first row is filled based on the dead productions N → t. Subsequent rows are filled based on the productions N → N₁N₂. In the second row, cell (2, z) is filled with all the words of length 2 that are the product of a letter from cell (1,x) and a letter from cell (1, y) for each rule N_z → N_x N_y . In the third row, cell (3, z) is filled with the words that are products of a word from row 2 and a word from row 1 in either order as long as the grammar includes a rule that generates that product. In the fourth row, the words can be made in three ways; the product of a letter and a 3-letter word, the product of two 2-letter words, the product of a 3-letter word and a single letter. When the table is complete, check cell (n, S) to see if w is among the words derived from S. 

For each of the following grammar- word pairs, construct such a table to determine whether the word can be generated by that grammar:

(i)

(ii)

(iii)

Transcribed Image Text:

S→XY X→XA | a | b Y→AY | a A-a w = babaa