CYK result de-transformation

Computer Science Asked on December 25, 2020

Suppose we have a rules derived from a treebank.
And in order to get a syntax tree of a given sentence we use the cyk algorithm.
In order to use the cyk we should convert the rules into chomsky normal form,
Such that all of my rules are A -> B C or A -> a (A,B,C are non-terminals and a is a terminal).
From the cyk we get the most probable tree, constituted from the cnf rules.
But what if we want to de-transform the tree to be constituted from the original rules?
We can expand very easily the Binary rules into the original.
But what about unit productions? for example; A->B->a transformed into A->a in cnf, how do we get the original unary rules path A->B->a?
Any ideas will be helpful.

One Answer

I don't think you can recover a unit production, unless (and this is probably the common case) the unit production is unambiguous. If there is only one derivation from a non-terminal to a particular terminal -- and it should be easy to figure that out while you are doing the transformation to CNF -- then you can record that derivation and reinsert it when you find the collapsed derivation in the CYK parse.

Answered by rici on December 25, 2020

Add your own answers!

Ask a Question

Get help from others!

© 2024 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP