wiki_research

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

context_free_grammar (1347B)


      1 # Context free grammar
      2 
      3 ## Concepts
      4 
      5 - [nonterminals]
      6 - [terminals]
      7 - [production]
      8 - [axiom]
      9 - [derivation_tree]
     10 - [context_free_language]
     11 - [proto_word]
     12 
     13 ## Equivalence
     14 
     15 - [context_free_grammar_pushdown_automaton_equivalence]
     16 - [context_free_grammar_equivalence]
     17 
     18 ## Subclasses
     19 
     20 - [context_free_grammar_deterministic]
     21 - [context_free_grammar_unambiguous]
     22   - [context_free_grammar_ambiguous]
     23 - [context_free_grammar_ultralinear]
     24   - [context_free_grammar_linear]
     25 - [context_free_grammar_bounded]
     26 - [context_free_grammar_polyslender]
     27 - [context_free_grammar_finite]
     28 - [inherently_ambiguous]
     29 
     30 ## Complexities
     31 
     32 - [logcfl]
     33 - [logdcfl]
     34 
     35 ## Problems
     36 
     37 - [context_free_grammar_equivalence]
     38 - [context_free_grammar_inclusion]
     39 - [context_free_grammar_universality]
     40 - [smallest_grammar_problem]
     41 - [context_free_grammar_membership]
     42 - [context_free_grammar_ambiguity_problem]
     43 
     44 ## Fields
     45 
     46 - [parsing]
     47 
     48 ## Extensions
     49 
     50 - [probabilistic_grammar]
     51 - [conjunctive_grammar]
     52 - [multiple_context_free_grammar]
     53 
     54 ## Results
     55 
     56 - [Greibach's_theorem]
     57 
     58 See also: [regular_language], [chomsky_hierarchy], [context_free_language], [inherently_ambiguous], [graph_grammar], [semilinear_set], [language_power_series], [Hyperedge_replacement_grammar]
     59 
     60 Up: [formal_language_theory], [formal_grammar], [context_free]
     61 
     62 Aliases: CFG, CFGs, context free grammars, context-free grammars