wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

context_free_grammar_equivalence_problem (624B)

      1 # Context free grammar equivalence problem
      2 
      3 The *context free grammar equivalence problem* is the [decision_problem] of testing, given two [CFGs], whether they are [CFG_equivalent]
      4 
      5 It is [undecidable] on [CFGs], by reduction from [CFG_universality]
      6 
      7 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]?
      8 
      9 Up: [formal_language_computational_problem], [context_free_grammar_equivalence]