Content deleted Content added
Note regarding Chomsky normal form. This is otherwise confusing if you come here directly from the Context-free grammar article |
|||
Line 25:
'''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===
| |||