Algoritmo CYK para gramática libre de contexto

Requisito previo: conversión de la gramática libre de contexto a la forma normal de Chomsky El
algoritmo CYK es un algoritmo de análisis para la gramática libre de contexto.
Para aplicar el algoritmo CYK a una gramática, debe estar en la forma normal de Chomsky. Utiliza un algoritmo de programación dinámica para saber si una string está en el lenguaje de una gramática.

Algoritmo:
Sea w la string de longitud n a analizar. Y G representan el conjunto de reglas en nuestra gramática con estado inicial S.

1. Construya una tabla DP de tamaño n × n.
2. Si w = e (string vacía) y S -> e es una regla en G, entonces aceptamos la string, de lo contrario la rechazamos.

3. For i = 1 to n:
     For each variable A:
        We check if A -> b is a rule and b = wi for some i:
           If so, we place A in cell (i, i) of our table. 

4. For l = 2 to n:
     For i = 1 to n-l+1:
          j = i+l-1
           For k = i to j-1:
              For each rule A -> BC: 
           We check if (i, k) cell contains B and (k + 1, j) cell contains C:
                If so, we put A in cell (i, j) of our table. 

5. We check if S is in (1, n):
     If so, we accept the string
     Else, we reject.

Ejemplo –
Sea nuestra gramática G:

S -> AB | BC
A -> BA | a
B -> CC | b
C -> AB | a 

Comprobamos si baaba está en L(G):

1. Primero insertamos reglas de longitud única en nuestra tabla.

   

2. Luego llenamos las celdas restantes de nuestra tabla.

   

3. Observamos que S está en la celda (1, 5), por lo tanto, la string baaba pertenece a L(G).

Complejidad de tiempo y espacio:

• Complejidad del tiempo –

  O(n3.|G|) 

  donde |G| es el número de reglas en la gramática dada.

• Complejidad espacial –

  O(n2)