// Ein Großbuchstabe folgt auf genau zwei weitere Großbuchstaben
X -> YZ

// oder
// Ein Großbuchstabe folgt auf genau einen Kleinbuchstaben
X -> a

// Pseudocode
 
 
FOR i=0 TO n-1
  Ti1 = { A | so dass A xi eine Regel in P ist}
  // Erste Zeile enthält alle Nichtterminale, welche das Eingabesymbol
  // an der entspr. Position ableitet
END
 
FOR j=1 TO n-1 // Für jede weitere Zeile
  FOR i=0 TO n-j // Für jede Zelle der Zeile (von links nach rechts) 
    FOR k=0 TO j-1 // Berechne jeweils zu betrachtendes Zellenpaar 
      k' = i + k; 
      j' = j - k; 
      Tij = Tij  { A | so dass A BC eine Regel in P ist, B in Tik und C in Tk'j' liegt}
      // Überprüfung für jedes Zellenpaar, ob Kombination dort enthaltener Nichtterminale
      // rechte Regelseite ergibt.
 
      // Das Terminalsymbol der dazu gehörenden linken Regelseite füge man Tij hinzu. 
      // Ti0 und T(i)(j)
      // Ti1 und T(i-1)(j-1)
      // Ti2 und T(i-2)(j-2)
      // usw.
    ENDFOR 
  ENDFOR
ENDFOR
 
 
IF S  Tij
  // Wort liegt in der Sprache vor
ELSE
  // Wort liegt in der Sprache nicht vor!
ENDIF
 

/**
* @desc Ueberprueft durch den CYK-Algorithmus, ob ein Wort in einer Sprache vorkommt
* @param vector regeln : Alle verfuegbaren Regeln
* @param string wort : zu Pruefendes Wort
* @return bool
*/
bool cyk(vector<cykStruct> regeln, string wort)
{
  int length = wort.length();
 
  //Matrix initialisieren
  string** matrix;
  matrix = matrixInit(wort.length());
 
 
  // Umformungen + Befuellen
  cout << "Zeile0: " << endl;
  for(int i=0; i<length; i++) // Fuer Zeile 0
  {
    matrix[i][0] = umformungZeile0(wort[i], regeln);
    cout << matrix[i][0] << ", ";
  }
  cout << endl;
 
 
  for(int j=1; j<length; j++)	// Zeile 1 bis Ende
  {
    for(int i=0; i<length-j; i++) // Fuer Jede Zelle der Zeile (von links nach rechts)
    {
      for(int k=0; k<j; k++) // Berechne Jeweilige Zellenpaar welches betrachtet werden soll
      {
        char ret;
        matrix[i][j] = "";
 
        if(istRegel(regeln, matrix[i][k], matrix[i+k+1][j-k-1], ret))
        {	
          matrix[i][j] = ret;
          break;
        }
      }
    }
  }
 
 
  // Pruefung ob Wort in der Sprache vorliegt, in dem ueberprueft wird,
  // ob unterster Eintrag der Dreiecksmatrix "S" entspricht
  if(regeln[0].von ==  matrix[0][length-1][0])
    return true;
 
 
  return false;	
}

// Regeldefinition
// von -> nach
// A   -> BB
// A   -> a
struct cykStruct
{
	char von;
	string nach;
};

/**
* @desc Sucht in den Regeln nach dem Vorkommen von c auf der Rechten Seite und liefert alle Vorkommen (linke Seite) zurueck
* @param char c : Zu umformendes Zeichen
* @param vector regeln : uebergabe der Regeln, in welchem die Pruefung stattfinden soll
* @return string
*/
string umformungZeile0(char c, vector<cykStruct> regeln)
{
  vector<cykStruct>::iterator it;
  string umformungen;
  for(it=regeln.begin(); it<regeln.end(); it++)
  {
    if(it->nach[0] == c)
    umformungen += it->von;
  }
 
  return umformungen;
}	
 

/**
* @desc Ueberprueft, ob es fuer zwei nebeneinander liegenden Feldern eine Regel gibt
* @param vector regeln : Alle verfuegbaren Regeln
* @param string feld1 : 1. zu pruefendes Feld
* @param string feld2 : 2. zu pruefendes Feld
* @param char &ret : Rueckgabe des Zeichens welches bei Erfolgsfall gefunden wurde
* @return bool
*/
bool istRegel(vector<cykStruct> regeln, string feld1, string feld2, char &ret)
{
  vector<cykStruct>::iterator it;
  for(int i=0; i<feld1.length(); i++)
    for(int j=0; j<feld2.length(); j++)
      for(it=regeln.begin(); it<regeln.end(); it++)
      {
        string tmp;
        tmp += feld1[i];
        tmp += feld2[j];
        string null;
        null = "0";
 
        if(it->nach == tmp)
        {
          ret = it->von;
            return true;
        }
      }
 
 
  ret = '0';
  return false;
}