1
$\begingroup$

So I have the following language:

C = {<G,w>|G is a CFG in Chomsky normal form and w has more than one parse tree in G}

How to prove that this language is in P (decidable in deterministic polynomial time)?

I tried to come up with a polynomial-time algorithm and tried to show a reduction to a different language in P, but couldn't figure it out.

$\endgroup$
0
$\begingroup$

You can modify the CYK parsing algorithm so that it counts the number of parse trees for each word.

Given a word $w = w_1 \ldots w_n$, for each $1 \leq i \leq j \leq n$ and non-terminal $A$, we will count the number of parse trees rooted at $A$ and generating $w_i \ldots w_j$. If $i = j$ then this number is either zero or one, depending on whether $A \to w_i$ is a rule. Otherwise, all parse trees are of the form $$A \to BC \to^* (w_i \ldots w_k) (w_{k+1} \ldots w_j)$$ and so if we know, for each $i \leq k < j$ and for each $B,C$ such that a rule $A \to BC$ exists, how many parse trees there are for $w_i \ldots w_k$ rooted at $B$ and for $w_{k+1} \ldots w_j$ rooted at $C$, then we can count the number of parse trees of $w_i \ldots w_j$ rooted at $A$.

You are interested in whether the number of parse trees of $w_1 \ldots w_n$ rooted at $S$ is larger than one or not. Therefore you can cap the numbers at two, thus avoiding large numbers and so reducing the running time.

$\endgroup$
1
  • $\begingroup$ Thanks! I tried a similar approach with CYK but the dots just didn't connect for me. I found another idea which I'm not sure about: Since the grammar is in CNF, the parsing of a word of length k is 2k-1 steps. Let's say the grammar has n production rules. So at each step, we have at most n rules to choose from. Thus, we can create ALL derivations at length 2k-1 at n^(2k-1) steps. Then we can check if at least 2 of those derivations create the string w. Since all production rules are part of the input, the time is polynomial at the length of the input. thoughts about this proof? $\endgroup$ Feb 10 at 16:07

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.