k_ambiguous_cfg (443B)
1 # K ambiguous CFG 2 3 A *k-ambiguous CFG* is a [CFG] where every [word] has at most k [parse_trees] 4 5 Special cases: 6 - k=1: [uCFGs] 7 - k=2: [2_ambiguous_CFGs] 8 9 It is an [open_problem] whether every k-ambiguous CFG can be written as a [language_union] of k [uCFGs], but within [bounded_CFGs] this is known to be true, cf [wich2005ambiguity] p181 point (iv). 10 11 Up: [k_ambiguous], [CFG] 12 13 See also: [infinitely_ambiguous_CFG], [Degree_of_ambiguity_cfg]