I have a linear grammar $G$ and a string $s$. $G$ is is not limited to right or left linear only but rather has a mix of rules of both types.

Is there an algorithm to determine whether $s \in L(G)$ in less than cubic time?

Converting to CNF and applying the CKY algorithm takes cubic time, and I am wondering if there is a more efficient algorithm.

  • $\begingroup$ You can apply CKY directly, without transforming (it's essentially a dynamic programming algorithm; transforming to CNF is needed only for guaranteed running time). It'll take quadratic time. $\endgroup$
    – user114966
    Oct 5 '20 at 12:11
  • $\begingroup$ @Dmitry Why would the CKY take quadratic time here? $\endgroup$
    – Eve George
    Oct 5 '20 at 14:36
  • 1
    $\begingroup$ CYK is a dynamic programming algorithm with $n^2$ states. For each state, computation takes $n^{k-1}$ time, where $k$ is the maximum number of nonterminals on the RHS of a rule. For CNF, $k=2$, for linear grammar, $k=1$. $\endgroup$
    – user114966
    Oct 5 '20 at 16:46
  • $\begingroup$ @Dmitry According to en.wikipedia.org/wiki/CYK_algorithm it loops over the input 3 times and thus the cubic time. Would this not be needed to be adjusted in some way to get to $O(n^{2})$? $\endgroup$
    – Eve George
    Oct 5 '20 at 20:52
  • 1
    $\begingroup$ Please don't make more work for other people by vandalizing your posts. By posting on the Stack Exchange (SE) network, you've granted a non-revocable right, under the CC BY-SA 4.0 license for SE to distribute that content. By SE policy, any vandalism will be reverted. If you want to know more about deleting a post, consider taking a look at: How does deleting work? $\endgroup$
    – Glorfindel
    Oct 8 '20 at 5:18

Yes, you can. As Dmitry explains, CYK parsing can be used to parse a linear grammar in $O(n^2)$ time, where $n$ is the length of the input word.

CYK parsing is a dynamic programming algorithm that sets $P[l,s,R]$ to be true if $a_{s .. s+l-1}$ can be generated from the non-terminal $R$, where $a_{1..n}$ is the input word.

Note that there is a recurrence relation that can be used to compute $P[l,s,R]$ from values of the form $P[l',s',R']$ with $l'<l$, in $O(1)$ time. In particular, if we have the rule $R \to b_1\cdots b_k Q c_1 \cdots c_m$, then we should set $P[l,s,R]$ to true if $a_{s .. s+k} = b_{1 .. k}$ and $P[l-k-m,s+k,Q]$ is true and $a_{s+l-m .. s+l-1} = c_{1 .. m}$. Do this for each rule with $R$ on the left-hand side. If none of them sets $P[l,s,R]$ to true, set $P[l,s,R]$ to false. This takes $O(1)$ time (treating the size of the grammar as a constant).

We repeat this for each of the entries $P[l,s,R]$. There are $O(n^2)$ such entries (treating the size of the grammar as a constant), and each entry takes $O(1)$ time to compute, so the entire algorithm runs in $O(n^2)$ time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.