Editing CYK algorithm (section)

===As pseudocode===
The algorithm in [[pseudocode]] is as follows:

 '''let''' the input be a string ''I'' consisting of ''n'' characters: ''a''<sub>1</sub> ... ''a''<sub>''n''</sub>.
 '''let''' the grammar contain ''r'' nonterminal symbols ''R''<sub>1</sub> ... ''R''<sub>''r''</sub>, with start symbol ''R''<sub>1</sub>.
 '''let''' ''P''[''n'',''n'',''r''] be an array of booleans. Initialize all elements of ''P'' to false.
 '''let''' ''back''[''n'',''n'',''r''] be an array of lists of backpointing triples. Initialize all elements of ''back'' to the empty list.
 
 '''for each''' ''s'' = 1 to ''n''
     '''for each''' unit production ''R''<sub>''v''</sub> &rarr; ''a''<sub>''s''</sub>
         '''set''' ''P''[''1'',''s'',''v''] = true
 
 '''for each''' ''l'' = 2 to ''n'' ''-- Length of span''
     '''for each''' ''s'' = 1 to ''n''-''l''+1 ''-- Start of span''
         '''for each''' ''p'' = 1 to ''l''-1 ''-- Partition of span''
             '''for each''' production ''R''<sub>''a''</sub>    &rarr; ''R''<sub>''b''</sub> ''R''<sub>''c''</sub>
                 '''if''' ''P''[''p'',''s'',''b''] and ''P''[''l''-''p'',''s''+''p'',''c''] '''then'''
                     '''set''' ''P''[''l'',''s'',''a''] = true, 
                     append <p,b,c> to ''back''[''l'',''s'',''a'']
 
 '''if''' ''P''[n,''1'',''1''] is true '''then'''
     ''I'' is member of language
     '''return''' ''back'' -- by ''retracing the steps through back, one can easily construct all possible parse trees of the string.''
 '''else'''
     '''return''' "not a member of language"

<div class="toccolours mw-collapsible mw-collapsed">

==== Probabilistic CYK (for finding the most probable parse) ====
Allows to recover the most probable parse given the probabilities of all productions.
<div class="mw-collapsible-content">

 '''let''' the input be a string ''I'' consisting of ''n'' characters: ''a''<sub>1</sub> ... ''a''<sub>''n''</sub>.
 '''let''' the grammar contain ''r'' nonterminal symbols ''R''<sub>1</sub> ... ''R''<sub>''r''</sub>, with start symbol ''R''<sub>1</sub>.
 '''let''' ''P''[''n'',''n'',''r''] be an array of real numbers. Initialize all elements of ''P'' to zero.
 '''let''' ''back''[''n'',''n'',''r''] be an array of backpointing triples.
 '''for each''' ''s'' = 1 to ''n''
   '''for each''' unit production ''R''<sub>''v''</sub> &rarr;''a''<sub>''s''</sub>
     '''set''' ''P''[''1'',''s'',''v''] = Pr(''R''<sub>''v''</sub> &rarr;''a''<sub>''s''</sub>)
 '''for each''' ''l'' = 2 to ''n'' ''-- Length of span''
   '''for each''' ''s'' = 1 to ''n''-''l''+1 ''-- Start of span''
     '''for each''' ''p'' = 1 to ''l''-1 ''-- Partition of span''       
       '''for each''' production ''R''<sub>''a''</sub> &rarr; ''R''<sub>''b''</sub> ''R''<sub>''c''</sub>
         prob_splitting = Pr(''R''<sub>''a''</sub> &rarr;''R''<sub>''b''</sub> ''R''<sub>''c''</sub>) * ''P''[''p'',''s'',''b''] * ''P''[''l''-''p'',''s''+''p'',''c'']
         '''if''' prob_splitting > ''P''[''l'',''s'',''a''] '''then''' 
           '''set''' ''P''[''l'',''s'',''a''] = prob_splitting
           '''set''' ''back''[''l'',''s'',''a''] = <p,b,c>
 
 '''if''' ''P''[n,''1'',''1''] > 0 '''then'''
     find the parse tree by retracing through ''back''
     '''return''' the parse tree
 '''else'''
     '''return''' "not a member of language"
</div>
</div>