context_free_grammar (1552B)
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 - [derivation] 13 14 ## Equivalence 15 16 - [context_free_grammar_pushdown_automaton_equivalence] 17 - [context_free_grammar_equivalence] 18 19 ## Subclasses 20 21 - [context_free_grammar_deterministic] 22 - [context_free_grammar_unambiguous] 23 - [context_free_grammar_ambiguous] 24 - [context_free_grammar_linear] 25 - [context_free_grammar_ultralinear] 26 - [context_free_grammar_metalinear] 27 - [context_free_grammar_superlinear] 28 - [context_free_grammar_finite_index] 29 - [context_free_grammar_bounded] 30 - [context_free_grammar_polyslender] 31 - [context_free_grammar_finite] 32 - [inherently_ambiguous] 33 34 ## Complexities 35 36 - [logcfl] 37 - [logdcfl] 38 39 ## Problems 40 41 - [context_free_grammar_equivalence] 42 - [context_free_grammar_inclusion] 43 - [context_free_grammar_universality] 44 - [smallest_grammar_problem] 45 - [context_free_grammar_membership] 46 - [context_free_grammar_ambiguity_problem] 47 - [context_free_grammar_enumeration] 48 49 ## Fields 50 51 - [parsing] 52 53 ## Extensions 54 55 - [probabilistic_grammar] 56 - [conjunctive_grammar] 57 - [multiple_context_free_grammar] 58 59 ## Results 60 61 - [Greibach's_theorem] 62 - [Chomsky-Schützenberger_theorem] 63 64 See also: [regular_language], [chomsky_hierarchy], [context_free_language], [inherently_ambiguous], [graph_grammar], [semilinear_set], [language_power_series], [Hyperedge_replacement_grammar] 65 66 Up: [formal_language_theory], [formal_grammar], [context_free] 67 68 Aliases: CFG, CFGs, context free grammars, context-free grammars