# 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?

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

## Related Questions

### What is the minimum number of parts required to split the sequence S to in order to obtain sequence T?

1  Asked on January 22, 2021 by powerful-blaster

### Does the set ALL_TM contain all Turing Machines?

1  Asked on January 18, 2021 by mkultra

1  Asked on January 18, 2021 by gaame

### For which c, d is Gap2SAT[c, d] in P (such that 0<c<d<1)?

1  Asked on January 17, 2021

### Why does the BFR (Bradley, Fayyad and Reina) algorithm assume clusters to be normally distributed around its centroid?

1  Asked on January 10, 2021 by r-dv

### How to find a condition which leads to deadlock in non-reentrant locks

1  Asked on January 9, 2021 by mb14

### Confusion converting BNF to regular expression

1  Asked on January 7, 2021 by haznut

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

2  Asked on January 7, 2021 by matt-kolson

### Knapsack Problem with Constraints on Item Values

1  Asked on January 7, 2021 by argenya

### Interpreting a proof of $2^mathbb{N}$ being uncountable

2  Asked on January 7, 2021 by 0xd34df00d

### 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

### CYK result de-transformation

1  Asked on December 25, 2020

### Proof that “the last vertex in any postordering (in a DFS) of G lies in a source component of G”

0  Asked on December 25, 2020 by user126667

### Are assembly languages untyped?

5  Asked on December 20, 2020 by a-sallai

### splitting of people betwen groups with group prioritiy list per person

1  Asked on December 15, 2020 by gomunkul

### DFA and equivalence relation

1  Asked on December 14, 2020 by nimrod

### In an NFA, what if there are no transitions out of an accept state but there are symbols left in the string?

1  Asked on December 14, 2020 by prms