Chomsky normal form enables a polynomial time algorithm to decide whether a string can be generated by a grammar.
The algorithm is pretty slick if you know dynamic programming...
If the length of your input ($I$) is $n$ then you take a 2d array ($A$) of dim $n$x$n$.
$A[i,j]$ denotes all the symbols in the grammar $G$ that can derive the sub-string $I(i,j)$.
So finally if $A[1,n]$ contains the start symbol ($S$) then it means that the string I can be derived by $S$ which is what we wanted to check.
def decide (string s,grammar G):
for i=1 to n:
N[i,i]=I[i] //as the substring of length one can be generated by only a
//end base case
for s=1 to n: //length of substring
for i=1 to n-s-1: //start index of substring
for j=i to i+s-1: //something else
if there exists a rule A->BC such that B belongs to N[i,j] and C
belongs to N[j+1,i+s-1] then add A to N[i,i+s-1]
if S belongs to N[1,n] then accept else reject.
I know that the indexes seem pretty crazy. But basically here's whats happening.
The base case is pretty clear I think.
In the inductive step we build the solution for a length $s$ substring from all the solutions with length less than $s$.
Say, you are finding the solution for length $5$ substring (
sub) starting at index $1$. Then you start a loop (something else part).....which checks whether there is a rule ($A->BC$) such that $B$ and $C$ derive two contiguous and disjoint substrings of sub and if so add all such $A$'s to $N[1,6]$.
Finally, if you have the start symbol in $N[1,n]$ then you accept!