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