AnswerBun.com

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 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP