CYK algorithm: Difference between revisions

Revision as of 10:37, 29 January 2015

Revision as of 00:38, 16 February 2015

Line 21:

'''for each''' ''i'' = 1 to ''n''

'''for each''' unit production ''R''_''j'' -> ''a''_''i''

set ''P''[''i1'',''1i'',''j''] = true

'''for each''' ''i'' = 2 to ''n'' ''-- Length of span''

'''for each''' ''j'' = 1 to ''n''-''i''+1 ''-- Start of span''

'''for each''' ''k'' = 1 to ''i''-1 ''-- Partition of span''

'''for each''' production ''R''_''A'' -> ''R''_''B'' ''R''_''C''

'''if''' ''P''[''jk'',''kj'',''B''] and ''P''[''ji''+-''k'',''ij''-+''k'',''C''] '''then''' set ''P''[''ji'',''ij'',''A''] = true

'''if''' any of ''P''[1n,''n1'',''x''] is true (''x'' is iterated over the set ''s'', where ''s'' are all the indices for ''R''_''s'') '''then'''

''S'' is member of language

'''else'''