Content deleted Content added
→References: add Sources section |
→As pseudocode: format code |
||
Line 17:
'''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.
'''for each''' ''s'' = 1 to ''n''
'''for each''' unit production ''R''<sub>''v''</sub> → ''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> → ''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
'''if''' ''P''[n,''1'',''1''] is true '''then'''
''I'' is member of language
'''else'''
''I'' is not member of language
<div class="toccolours mw-collapsible mw-collapsed">
| |||