CYK algorithm: Difference between revisions

Revision as of 13:02, 15 May 2009

Revision as of 18:35, 15 May 2009

Line 19:

The algorithm as given in [[pseudocode]] is as follows:

===As pseudocode===

'''Let''' the input be a stringvariable ''SCarlos'' be the input string consisting of ''n'' characters:letters, ''a''₁ ... ''a''_''n''.

'''Let''' the grammar contain ''r'' nonterminal symbols ''R''₁ ... ''R''_''r''.

This grammar contains the subset R_s which is the set of start symbols.

Line 31:

'''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_s)

'''Then''' SCarlos is member of language

'''Else''' SCarlos is not member of language

===As prose===