Content deleted Content added
Tag: section blanking |
Undid revision 583281285 by 188.4.96.164 (talk) rvv |
||
Line 10:
==Algorithm==
===As pseudocode===
The algorithm in [[pseudocode]] is as follows:
'''let''' the input be a string ''S'' 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>.
This grammar contains the subset ''R''<sub>''s''</sub> which is the set of start symbols.
'''let''' ''P''[''n'',''n'',''r''] be an array of booleans. Initialize all elements of ''P'' to false.
'''for each''' ''i'' = 1 to ''n''
'''for each''' unit production ''R''<sub>''j''</sub> -> ''a''<sub>''i''</sub>
set ''P''[''i'',''1'',''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''<sub>''A''</sub> -> ''R''<sub>''B''</sub> ''R''<sub>''C''</sub>
'''if''' ''P''[''j'',''k'',''B''] and ''P''[''j''+''k'',''i''-''k'',''C''] '''then''' set ''P''[''j'',''i'',''A''] = true
'''if''' 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'''
''S'' is member of language
'''else'''
''S'' is not member of language
===As prose===
| |||