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.
- Construya una tabla DP de tamaño n × n.
- Si w = e (string vacía) y S -> e es una regla en G, entonces aceptamos la string, de lo contrario la rechazamos.
-
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.
-
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.
-
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):
- Primero insertamos reglas de longitud única en nuestra tabla.
- Luego llenamos las celdas restantes de nuestra tabla.
- 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