CYK algorithm: Difference between revisions

Revision as of 19:22, 10 February 2007

Revision as of 19:23, 10 February 2007

Line 27:

===Informally===

{| class="wikitable"

|-

! header 1

! header 2

! header 3

|-

| row 1, cell 1

| row 1, cell 2

| row 1, cell 3

|-

| row 2, cell 1

| row 2, cell 2

| row 2, cell 3

|}

In informal terms, this algorithm considers every possible substring of the string of letters and sets P[i,j,k] to be true if the substring of letters starting from i of length j can be generated from R_k. Once it has considered substrings of length 1, it goes on to substrings of length 2, and so on. For substrings of length 2 and greater, it considers every possible partition of the substring into two halves, and checks to see if there is some production P → Q R such that Q matches the first half and R matches the second half. If so, it records P as matching the whole substring. Once this process is completed, the sentence is recognized by the grammar if the substring containing the entire string is matched by the start symbol.