Determine whether the string w = aabbb is in the language generated by the
grammar
First note that w 11 = a, so V 11 is the set of all variables that immediately
derive a, that is, V 11 = {A}. Since w 22 = a, we also have V 22 = {A} and, similarly ,
Now we use (6.8) to get
Since V 11 = {A} and V 22 = {A}, the set consists of all variables that occur on the
left side of a production whose right side is AA. Since there are none, V12 is
empty. Next,
so the required right side is AB, and we have V 23 = {S, B}. A straightforward
argument along these lines then gives
so that w L (G).
The CYK algorithm, as described here, determines membership for any
grammar
First note that w 11 = a, so V 11 is the set of all variables that immediately
derive a, that is, V 11 = {A}. Since w 22 = a, we also have V 22 = {A} and, similarly ,
Now we use (6.8) to get
Since V 11 = {A} and V 22 = {A}, the set consists of all variables that occur on the
left side of a production whose right side is AA. Since there are none, V12 is
empty. Next,
so the required right side is AB, and we have V 23 = {S, B}. A straightforward
argument along these lines then gives
so that w L (G).
The CYK algorithm, as described here, determines membership for any