Context-free language

A grammar is context-free when each production has one nonterminal on its left.

A context-free grammar consists of terminal and nonterminal alphabets, a start symbol, and productions whose left side is one nonterminal. A derivation records the order of substitutions, while a parse tree records their hierarchical structure, so several derivations can represent one parse tree.

A right-linear grammar has productions of the form $A\to wB$ or $A\to w$, where $A,B$ are nonterminals and $w$ is a terminal word, possibly empty. Each right-hand side has at most one nonterminal, at its right end. Such grammars generate exactly regular languages: regard nonterminals as states and expand each terminal word into a finite path to another state or an accepting endpoint. Conversely the transition graph of a deterministic finite automaton gives these productions directly.

A nonterminal symbol is a grammar symbol that may be replaced by a production and need not occur in a completed word.

A terminal symbol belongs to the alphabet of completed words and is not replaced by a grammar production.

A production rule specifies a permitted replacement during a grammar derivation. In a context-free grammar it has the form $A\to \alpha$, with one nonterminal $A$ on the left.

A sentence of a grammar is a terminal word derivable from its start symbol.

A grammar derivation is a finite sequence of words in which each step replaces one occurrence of a production's left side by its right side. A leftmost derivation always replaces the leftmost available nonterminal.

A parse tree places the start symbol at its root, the symbols on the right side of a production at the children of its left-side nonterminal, and terminal symbols at its leaves. Reading the leaves from left to right gives the tree's yield.

Two grammars are equivalent when they generate the same formal language.

Two grammars over a common terminal alphabet are isomorphic when a bijection between their nonterminal alphabets maps one start symbol to the other and maps their productions bijectively after being extended to fix every terminal symbol. Isomorphic grammars are equivalent.

A context-free grammar is in Chomsky normal form when every production has the form $A\to BC$ or $A\to a$, with $A,B,C$ nonterminals and $a$ a terminal. If the empty word belongs to the language, one commonly also permits the exceptional rule $S\to ϵ$ under the usual restriction on the start symbol.

An epsilon production is a grammar production whose right-hand side is the empty word.

A unit production replaces one nonterminal by one nonterminal and emits no terminal symbols.

To convert a context-free grammar to Chomsky normal form, first add a fresh start symbol. Remove epsilon productions, retaining the exceptional start production only when the empty word is to remain in the language; then remove unit productions and symbols that cannot participate in a terminal derivation. Replace each terminal occurring in a right-hand side of length at least two by a new nonterminal that produces that terminal. Finally split every right-hand side of length greater than two into binary productions using fresh nonterminals.

A Chomsky-normal-form parse tree for a word of length $n\ge 1$ has $n$ terminal productions and $n-1$ binary productions. Every derivation represented by the tree therefore has exactly $2n-1$ steps.

The CYK algorithm decides membership in a context-free language given by a grammar in Chomsky normal form. It records, for every substring, the nonterminals that derive that substring and combines adjacent substrings using binary productions. For a word of length $n$ and a fixed grammar, it runs in $O(n^3)$ time.

Weak Chomsky normal form additionally permits ternary productions $A\to BCD$. Compressing a two-step pattern $A\to BE$, $E\to CD$ into $A\to BCD$ preserves its generated yields whenever the intermediate variable has no other role, and saves one derivation step each time the pattern is used.

The productions $S\to 0S0\mid 1S1\mid 00\mid 11$ generate exactly the nonempty binary palindromes of even length.

The intersection of a context-free language with a regular language is context-free, because a pushdown automaton and a finite automaton can be run in product.

If context-free grammars with disjoint nonterminal alphabets have start symbols $S_1,S_2$, adjoining a new start symbol and the production $S\to S_1{S}_2$ gives a context-free grammar for the concatenation of their languages.

If a context-free grammar for $L$ has start symbol $S$, adjoining a new start symbol $S_0$ and productions $S_0\to ϵ\mid S{S}_0$ gives a context-free grammar for the Kleene star $L^{\ast }$.

Every context-free language over a one-symbol alphabet is a regular language. Equivalently, the set of word lengths of a unary context-free language is ultimately periodic. This follows, for example, from the one-dimensional case of Parikh's theorem.

A context-free grammar can enforce sums such as $0^n{1}^m{0}^{n+m}$ by nesting one matched terminal pair for each independent count.

The languageis context-free. The grammarnests the $a,d$ dependency around the $b,c$ dependency.