wiki_research

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

context_free_grammar_equivalence_problem (442B)

      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 - for [uCFGs] (or with multiplicity of [parse_trees]): [context_free_grammar_unambiguous_equivalence_problem]
      8 
      9 Up: [formal_language_computational_problem], [context_free_grammar_equivalence]