wiki_research

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

context_free_grammar_equivalence_problem (597B)

      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]. It is already [undecidable] on [linear_CFGs], cf [linear_CFG_equivalence]
      6 
      7 - for [uCFGs] (or with multiplicity of [parse_trees]): [context_free_grammar_unambiguous_equivalence_problem]
      8 - [DPDA_equivalence_problem]
      9 
     10 Up: [formal_language_computational_problem], [context_free_grammar_equivalence]
     11 
     12 Aliases: CFG equivalence problem, CFG equivalence