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