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!

Related Questions

Does the set ALL_TM contain all Turing Machines?

1  Asked on January 18, 2021 by mkultra


Irregularity of ${0^x1^y : y nmid x}$

2  Asked on January 7, 2021 by matt-kolson


2-dimensional ranking of multiple arrays

1  Asked on January 6, 2021 by albert-hendriks


Lambda calculus simplification excercise

1  Asked on January 1, 2021 by user126373


Calculating the set field of associative cache

2  Asked on January 1, 2021 by user3125670


Are assembly languages untyped?

5  Asked on December 20, 2020 by a-sallai


DFA and equivalence relation

1  Asked on December 14, 2020 by nimrod


Ask a Question

Get help from others!

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