Context-free grammar (CFG) is a kind of formal grammar whose production rule has a single nonterminal on its left-hand side (the “head”.)
The languages produced by CFGs are called context-free languages.
Subtopics
- derivation and ambiguous grammar
- parsing context-free grammar
- Chomsky normal form and CYK algorithm
- pumping lemma for context-free languages
- BNF notation
- pushdown automaton
Characteristics
Restricting heads to a single symbol is a definite character of the context-free grammar. For more unrestricted grammar, the head can have multiple symbols. For example:
C -> A C A | B A // CFG
C D -> A C D A | B A // Not CFG
Formalism
- The alphabet
: A set of terminals - A set of variables (or nonterminals)
- A start variable
- A set of production rules
- with the form
variable -> string of variables and terminals
- with the form