context_free_grammar_unambiguous_equivalence_problem (708B)
1 # Context free grammar unambiguous equivalence problem 2 3 It is an [open_problem] whether CFG equivalence is decidable when the input are two [uCFGs]. Same thing for the problem on arbitrary [CFGs] where we want equivalence in [bag_semantics] i.e., do the two [CFGs] recognize the same language with the same number of [parse_trees] for each [word]? 4 5 cf https://cstheory.stackexchange.com/questions/38598/is-equivalence-of-unambiguous-context-free-languages-decidable 6 7 By contrast [language_inclusion] is [undecidable] because [DPDA_inclusion] is [undecidable] 8 9 Up: [context_free_grammar_equivalence_problem], [uCFGs] 10 11 Aliases: unambiguous CFG equivalence problem, equivalence context free grammar unambiguous