title: CYK algorithm implementation C++
body: <p>I've been trying to implement the CYK algorithm based on the pseudocode given by wikipedia, however I can't seem to get it right and I don't know what is wrong with the code. My best guess is that my indexes are wrong, since the pseudocode does not use array indexing.</p>
  
  <p>This is the grammar I'm testing:<br>
  / --> U1V1 | U2V2 | V1V1 | V2V2 | a | b<br>
  S --> U1V1 | U2V2 | V1V1 | V2V2 | a | b<br>
  V1 --> a<br>
  V2 --> b<br>
  U1 --> V1S<br>
  U2 --> V2S<br>
  This grammar accepts palindromes, so "baab" shoulde be accepted, however it is not being accepted as part of the grammar<br><br> 
  Here is the code:</p>
  
  <pre><code>int n = (int)S.size();
          std::vector&lt;std::vector&lt;std::vector&lt;bool&gt;&gt;&gt; P(n, std::vector&lt;std::vector&lt;bool&gt;&gt;(n, std::vector&lt;bool&gt;(startVariables.size(), false)));
  
          for(int i = 0; i &lt; n; i++)
          {
              for(int j = 0; j &lt; productions.size(); j++)
              {
                      std::vector&lt;std::string&gt; prods = getProductionsFromVariable(productions[j].variable);
                  for(int k = 0; k &lt; prods.size(); k++)
                  {
                      if(prods[k][0] == S[i] &amp;&amp; !isMayus(prods[k][0]) &amp;&amp; !isnumber(prods[k][0]))
                      {
                          P[0][i][j] = true;
                      }
                  }
              }
          }
  
          for(int i = 1; i &lt; n; i++)
          {
              for(int j = 0; j &lt; n-i; j++)
              {
                  for(int k = 0; k &lt; i; k++)
                  {
                      for(int l = 0; l &lt; startVariables.size(); l++)
                      {
                          std::vector&lt;std::string&gt; prods = getProductionsFromVariable(startVariables[l]);
                          for(int m = 0; m &lt; prods.size(); m++)
                          {
                              if(getNumberOfVars(prods[m]) &gt;= 2)
                              {
                                  std::vector&lt;std::string&gt; subProds = getNumberedVariables(prods[m]);
                                  int A = getStartVariablePos(startVariables[l]);
                                  int B = getStartVariablePos(subProds[0]);
                                  int C = getStartVariablePos(subProds[1]);
                                  if(P[k][j][B] &amp;&amp; P[i-k][j+k][C])
                                      P[i][j][A] = true;
                              }
                          }
                      }
                  }
              }
          }
  
          bool cyk = false;
          for(int i = 0; i &lt; startVariables.size(); i++)
          {
              if(P[n-1][0][i])
                  cyk = true;
          }
          return cyk;
  </code></pre>
  
  <p>The auxiliary functions just return all the given productions of a variable and their index in the vector of variables {/,S,V1,V2,U1,U2} <br><br></p>
  
  <p>This grammar (in CNF) comes from the converted grammar S>aSa|bSb|aa|bb|a|b (not in CNF)</p>
  
  <p>Any help would be greatly appreciated</p>