wiki_research

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

context_free_grammar_unambiguous (873B)

      1 # Unambiguous CFG (uCFG)
      2 
      3 An *unambiguous CFG* is a [context_free_grammar] where for every [word] in the [formal_language] there is exactly one [derivation_tree]
      4 
      5 [parsing] for an unambiguous CFG can be done in [quadratic_time]
      6 - https://cstheory.stackexchange.com/a/10504
      7 
      8 There are some [CFLs] admitting no uCFG (namely, those that are not [uCFLs]), and there is no computable function bounding the conciseness gap between uCFGs and [CFGs]: there are [uCFLs] where the smallest uCFG is arbitrarily larger than the smallest CFG.
      9 
     10 [Computational_problems]:
     11 
     12 - [unambiguous_cfg_equivalence_problem]
     13 - [unambiguous_cfg_inclusion_problem]
     14 - [unambiguous_cfg_universality]
     15 
     16 Up: [unambiguity], [context_free_grammar]
     17 
     18 See also: [inherently_ambiguous], [context_free_grammar_k_ambiguous], [CFG_ambiguous]
     19 
     20 Aliases: unambiguous CFG, unambiguous CFGs, CFG unambiguous, uCFG, uCFGs