#lexicalized-pcfg

Question 1: Single choice

A lexicalized PCFG in Chomsky normal form has rules such as $\mathrm{S}(\textit{saw}) \to \mathrm{NP}(\textit{man})\ \mathrm{VP}(\textit{saw})$ , where every symbol carries a head word. A CKY-style dynamic program fills a table $\pi[i, j, k, X]$ : the best probability of a subtree rooted in $X(w_k)$ spanning words $i \ldots j$ . For a sentence of $n$ words and $\lvert N \rvert$ non-terminals, how does its running time grow?

$O(n^5 \lvert N \rvert^3)$ 1
$O(n^3 \lvert N \rvert^3)$ 2
$O(n^4 \lvert N \rvert^3)$ 3
$O(n^3 \lvert N \rvert^3 \lvert V \rvert^2)$ , with $\lvert V \rvert$ the vocabulary size4

Timed test