SUPER IMPORTANT-Updating

[pristinawang]

CKY Algorithm

1. top-down approach to cky parser is 9 times more efficient than bottom-up approach
2. 4 Different Variants for recognizer and their runtime are different

$$ \text{Time Complexity of variant 1} = O(N^3 \cdot K^3) $$

$$ \text{Time Complexity of variant 2} = O(N^3 \cdot K^2 \cdot D) $$

$$ \text{Time Complexity of variant 3} = O(N^3 \cdot K^2) $$

$$ \text{Time Complexity of variant 1} = O(N^3 \cdot G) $$

$$K = Number \ of \ Non-Terminals$$

$$D = Rules \ with \ YZ \ on \ RHS$$

$$G = Searching \ entire \ Grammar$$