|
The algorithm in [[pseudocode]] is as follows:
'''Letlet''' the input be a string ''S'' consisting of ''n'' characters: ''a''<sub>1</sub> ... ''a''<sub>''n''</sub>.
'''Letlet''' the grammar contain ''r'' nonterminal symbols ''R''<sub>1</sub> ... ''R''<sub>''r''</sub>.
This grammar contains the subset ''R''<sub>''s''</sub> which is the set of start symbols.
'''Letlet''' ''P''[''n'',''n'',''r''] be an array of booleans. Initialize all elements of ''P'' to false.
'''Forfor each''' ''i'' = 1 to ''n''
'''Forfor each''' unit production ''R''<sub>''j''</sub> -> ''a''<sub>''i''</sub>,
'''set''' ''P''[''i'',1,''j''] = true.
'''Forfor each''' ''i'' = 2 to ''n'' ''-- Length of span''
'''Forfor each''' ''j'' = 1 to ''n''-''i''+1 ''-- Start of span''
'''Forfor each''' ''k'' = 1 to ''i''-1 ''-- Partition of span''
'''Forfor each''' production ''R''<sub>''A''</sub> -> ''R''<sub>''B''</sub> ''R''<sub>''C''</sub>
'''Ifff''' ''P''[''j'',''k'',''B''] and ''P''[''j''+''k'',''i''-''k'',''C''] '''then''' set ''P''[''j'',''i'',''A''] = true
'''Ifif''' any of ''P''[1,''n'',''x''] is true (''x'' is iterated over the set ''s'', where ''s'' are all the indices for ''R''<sub>''s''</sub>) '''then'''
'''Then''' ''S'' is member of language
'''Elseelse'''
''S'' is not member of language
===As prose===
| 