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)  

Publicación traducida automáticamente

Artículo escrito por mayankjoshi0841 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *