Context-free grammar

A production rule in R is formalized mathematically as a pair ${\displaystyle (\alpha ,\beta )\in R}$, where ${\displaystyle \alpha \in V}$ is a nonterminal and ${\displaystyle \beta \in (V\cup \Sigma )^{*}}$ is a string of variables and/or terminals; rather than using ordered pair notation, production rules are usually written using an arrow operator with ${\displaystyle \alpha }$ as its left hand side and β as its right hand side: ${\displaystyle \alpha \rightarrow \beta }$.

It is allowed for β to be the empty string, and in this case it is customary to denote it by ε. The form ${\displaystyle \alpha \rightarrow \varepsilon }$ is called an ε-production.[6]

It is common to list all right-hand sides for the same left-hand side on the same line, using | (the pipe symbol) to separate them. Rules ${\displaystyle \alpha \rightarrow \beta _{1}}$ and ${\displaystyle \alpha \rightarrow \beta _{2}}$ can hence be written as ${\displaystyle \alpha \rightarrow \beta _{1}\mid \beta _{2}}$. In this case, ${\displaystyle \beta _{1}}$ and ${\displaystyle \beta _{2}}$ are called the first and second alternative, respectively.

For any strings ${\displaystyle u,v\in (V\cup \Sigma )^{*}}$, we say u directly yields v, written as ${\displaystyle u\Rightarrow v\,}$, if ${\displaystyle \exists (\alpha ,\beta )\in R}$ with ${\displaystyle \alpha \in V}$ and ${\displaystyle u_{1},u_{2}\in (V\cup \Sigma )^{*}}$ such that ${\displaystyle u\,=u_{1}\alpha u_{2}}$ and ${\displaystyle v\,=u_{1}\beta u_{2}}$. Thus, v is a result of applying the rule ${\displaystyle (\alpha ,\beta )}$ to u.

For any strings ${\displaystyle u,v\in (V\cup \Sigma )^{*},}$ we say u yields v or v is derived from u if there is a positive integer k and strings ${\displaystyle u_{1},\cdots ,u_{k}\in (V\cup \Sigma )^{*}}$ such that ${\displaystyle u=u_{1}\Rightarrow u_{2}\Rightarrow \cdots \Rightarrow u_{k}=v}$. This relation is denoted ${\displaystyle u{\stackrel {*}{\Rightarrow }}v}$, or ${\displaystyle u\Rightarrow \Rightarrow v}$ in some textbooks. If ${\displaystyle k\geq 2}$, the relation ${\displaystyle u{\stackrel {+}{\Rightarrow }}v}$ holds. In other words, ${\displaystyle ({\stackrel {*}{\Rightarrow }})}$ and ${\displaystyle ({\stackrel {+}{\Rightarrow }})}$ are the reflexive transitive closure (allowing a string to yield itself) and the transitive closure (requiring at least one step) of ${\displaystyle (\Rightarrow )}$, respectively.

The language of a grammar ${\displaystyle G=(V,\Sigma ,R,S)}$ is the set

${\displaystyle L(G)=\{w\in \Sigma ^{*}:S{\stackrel {*}{\Rightarrow }}w\}}$

of all terminal-symbol strings derivable from the start symbol.

A language L is said to be a context-free language (CFL), if there exists a CFG G, such that ${\displaystyle L\,=\,L(G)}$.

Non-deterministic pushdown automata recognize exactly the context-free languages.

The grammar ${\displaystyle G=(\{S\},\{a,b\},P,S)}$, with productions

S → aSa,

S → bSb,

S → ε,

is context-free. It is not proper since it includes an ε-production. A typical derivation in this grammar is

S → aSa → aaSaa → aabSbaa → aabbaa.

This makes it clear that ${\displaystyle L(G)=\{ww^{R}:w\in \{a,b\}^{*}\}}$. The language is context-free, however, it can be proved that it is not regular.

If the productions

S → a,

S → b,

are added, a context-free grammar for the set of all palindromes over the alphabet { a, b } is obtained.[7]

The canonical example of a context-free grammar is parenthesis matching, which is representative of the general case. There are two terminal symbols "(" and ")" and one nonterminal symbol S. The production rules are

S → SS,

S → (S),

S → ()

The first rule allows the S symbol to multiply; the second rule allows the S symbol to become enclosed by matching parentheses; and the third rule terminates the recursion.[8]

A second canonical example is two different kinds of matching nested parentheses, described by the productions:

S → SS

S → ()

S → (S)

S → []

S → [S]

with terminal symbols [ ] ( ) and nonterminal S.

The following sequence can be derived in that grammar:

([ [ [ ()() [ ][ ] ] ]([ ]) ])

In a context-free grammar, we can pair up characters the way we do with brackets. The simplest example:

S → aSb

S → ab

This grammar generates the language ${\displaystyle \{a^{n}b^{n}:n\geq 1\}}$, which is not regular (according to the pumping lemma for regular languages).

The special character ε stands for the empty string. By changing the above grammar to

S → aSb

S → ε

we obtain a grammar generating the language ${\displaystyle \{a^{n}b^{n}:n\geq 0\}}$ instead. This differs only in that it contains the empty string while the original grammar did not.

A context-free grammar for the language consisting of all strings over {a,b} containing an unequal number of a's and b's:

S → T | U

T → VaT | VaV | TaV

U → VbU | VbV | UbV

V → aVbV | bVaV | ε

Here, the nonterminal T can generate all strings with more a's than b's, the nonterminal U generates all strings with more b's than a's and the nonterminal V generates all strings with an equal number of a's and b's. Omitting the third alternative in the rules for T and U doesn't restrict the grammar's language.

Another example of a non-regular language is ${\displaystyle \{{\text{b}}^{n}{\text{a}}^{m}{\text{b}}^{2n}:n\geq 0,m\geq 0\}}$. It is context-free as it can be generated by the following context-free grammar:

S → bSbb | A

A → aA | ε

The formation rules for the terms and formulas of formal logic fit the definition of context-free grammar, except that the set of symbols may be infinite and there may be more than one start symbol.

Here is a context-free grammar for syntactically correct infix algebraic expressions in the variables x, y and z:

1. S → x
2. S → y
3. S → z
4. S → S + S
5. S → S – S
6. S → S * S
7. S → S / S
8. S → (S)

This grammar can, for example, generate the string

(x + y) * x – z * y / (x + x)

as follows:

S

→ S – S (by rule 5)

→ S * S – S (by rule 6, applied to the leftmost S)

→ S * S – S / S (by rule 7, applied to the rightmost S)

→ (S) * S – S / S (by rule 8, applied to the leftmost S)

→ (S) * S – S / (S) (by rule 8, applied to the rightmost S)

→ (S + S) * S – S / (S) (by rule 4, applied to the leftmost S)

→ (S + S) * S – S * S / (S) (by rule 6, applied to the fourth S)

→ (S + S) * S – S * S / (S + S) (by rule 4, applied to the rightmost S)

→ (x + S) * S – S * S / (S + S) (etc.)

→ (x + y) * S – S * S / (S + S)

→ (x + y) * x – S * S / (S + S)

→ (x + y) * x – z * S / (S + S)

→ (x + y) * x – z * y / (S + S)

→ (x + y) * x – z * y / (x + S)

→ (x + y) * x – z * y / (x + x)

Note that many choices were made underway as to which rewrite was going to be performed next. These choices look quite arbitrary. As a matter of fact, they are, in the sense that the string finally generated is always the same. For example, the second and third rewrites

→ S * S – S (by rule 6, applied to the leftmost S)

→ S * S – S / S (by rule 7, applied to the rightmost S)

could be done in the opposite order:

→ S – S / S (by rule 7, applied to the rightmost S)

→ S * S – S / S (by rule 6, applied to the leftmost S)

Also, many choices were made on which rule to apply to each selected S. Changing the choices made and not only the order they were made in usually affects which terminal string comes out at the end.

Let's look at this in more detail. Consider the parse tree of this derivation:

Starting at the top, step by step, an S in the tree is expanded, until no more unexpanded Ses (nonterminals) remain. Picking a different order of expansion will produce a different derivation, but the same parse tree. The parse tree will only change if we pick a different rule to apply at some position in the tree.

But can a different parse tree still produce the same terminal string, which is (x + y) * x – z * y / (x + x) in this case? Yes, for this particular grammar, this is possible. Grammars with this property are called ambiguous.

For example, x + y * z can be produced with these two different parse trees:

However, the language described by this grammar is not inherently ambiguous: an alternative, unambiguous grammar can be given for the language, for example:

T → x

T → y

T → z

S → S + T

S → S – T

S → S * T

S → S / T

T → (S)

S → T,

once again picking S as the start symbol. This alternative grammar will produce x + y * z with a parse tree similar to the left one above, i.e. implicitly assuming the association (x + y) * z, which does not follow standard order of operations. More elaborate, unambiguous and context-free grammars can be constructed that produce parse trees that obey all desired operator precedence and associativity rules.

The parsing problem, checking whether a given word belongs to the language given by a context-free grammar, is decidable, using one of the general-purpose parsing algorithms:

• CYK algorithm (for grammars in Chomsky normal form)
• Earley parser
• GLR parser
• LL parser (only for the proper subclass of for LL(k) grammars)

Context-free parsing for Chomsky normal form grammars was shown by Leslie G. Valiant to be reducible to boolean matrix multiplication, thus inheriting its complexity upper bound of O(n^2.3728639).[15][16][note 1] Conversely, Lillian Lee has shown O(n^3−ε) boolean matrix multiplication to be reducible to O(n^3−3ε) CFG parsing, thus establishing some kind of lower bound for the latter.[17]

A nonterminal symbol ${\displaystyle X}$ is called productive, or generating, if there is a derivation ${\displaystyle X{\stackrel {*}{\Rightarrow }}w}$ for some string ${\displaystyle w}$ of terminal symbols. ${\displaystyle X}$ is called reachable if there is a derivation ${\displaystyle S{\stackrel {*}{\Rightarrow }}\alpha X\beta }$ for some strings ${\displaystyle \alpha ,\beta }$ of non-terminal and terminal symbols from the start symbol. ${\displaystyle X}$ is called useless if it is unreachable or unproductive. ${\displaystyle X}$ is called nullable if there is a derivation ${\displaystyle X{\stackrel {*}{\Rightarrow }}\varepsilon }$. A rule ${\displaystyle X\rightarrow \varepsilon }$ is called an ε-production. A derivation ${\displaystyle X{\stackrel {+}{\Rightarrow }}X}$ is called a cycle.

Algorithms are known to eliminate from a given grammar, without changing its generated language,

• unproductive symbols,[18][note 2]
• unreachable symbols,[20][21][22]
• ε-productions, with one possible exception,[note 3][23] and
• cycles.[note 4]

In particular, an alternative containing a useless nonterminal symbol can be deleted from the right-hand side of a rule. Such rules and alternatives are called useless.[24]

In the depicted example grammar, the nonterminal D is unreachable, and E is unproductive, while C → C causes a cycle. Hence, omitting the last three rules doesn't change the language generated by the grammar, nor does omitting the alternatives "| Cc | Ee" from the right-hand side of the rule for S.

A context-free grammar is said to be proper if it has neither useless symbols nor ε-productions nor cycles.[25] Combining the above algorithms, every context-free grammar not generating ε can be transformed into a weakly equivalent proper one.

It is decidable whether a given grammar is a regular grammar,[26] as well as whether it is an LL(k) grammar for a given k≥0.[27]^:233 If k is not given, the latter problem is undecidable.[27]^:252

Given a context-free language, it is neither decidable whether it is regular,[28] nor whether it is an LL(k) language for a given k.[27]^:254

There are algorithms to decide whether a language of a given context-free language is empty, as well as whether it is finite.[29]

Given a CFG, does it generate the language of all strings over the alphabet of terminal symbols used in its rules?[30][31]

A reduction can be demonstrated to this problem from the well-known undecidable problem of determining whether a Turing machine accepts a particular input (the halting problem). The reduction uses the concept of a computation history, a string describing an entire computation of a Turing machine. A CFG can be constructed that generates all strings that are not accepting computation histories for a particular Turing machine on a particular input, and thus it will accept all strings only if the machine doesn't accept that input.

Given two CFGs, do they generate the same language?[31][32]

The undecidability of this problem is a direct consequence of the previous: it is impossible to even decide whether a CFG is equivalent to the trivial CFG defining the language of all strings.

Given two CFGs, can the first one generate all strings that the second one can generate?[31][32]

If this problem was decidable, then language equality could be decided too: two CFGs G1 and G2 generate the same language if L(G1) is a subset of L(G2) and L(G2) is a subset of L(G1).

Using Greibach's theorem, it can be shown that the two following problems are undecidable:

• Given a context-sensitive grammar, does it describe a context-free language?
• Given a context-free grammar, does it describe a regular language?[31][32]

Given a CFG, is it ambiguous?

The undecidability of this problem follows from the fact that if an algorithm to determine ambiguity existed, the Post correspondence problem could be decided, which is known to be undecidable.

Given two CFGs, is there any string derivable from both grammars?

If this problem was decidable, the undecidable Post correspondence problem could be decided, too: given strings ${\displaystyle \alpha _{1},\ldots ,\alpha _{N},\beta _{1},\ldots ,\beta _{N}}$ over some alphabet ${\displaystyle \{a_{1},\ldots ,a_{k}\}}$, let the grammar ${\displaystyle G_{1}}$ consist of the rule

${\displaystyle S\to \alpha _{1}S\beta _{1}^{rev}|\cdots |\alpha _{N}S\beta _{N}^{rev}|b}$;

where ${\displaystyle \beta _{i}^{rev}}$ denotes the reversed string ${\displaystyle \beta _{i}}$ and ${\displaystyle b}$ doesn't occur among the ${\displaystyle a_{i}}$; and let grammar ${\displaystyle G_{2}}$ consist of the rule

${\displaystyle T\to a_{1}Ta_{1}|\cdots |a_{k}Ta_{k}|b}$;

Then the Post problem given by ${\displaystyle \alpha _{1},\ldots ,\alpha _{N},\beta _{1},\ldots ,\beta _{N}}$ has a solution if and only if ${\displaystyle L(G_{1})}$ and ${\displaystyle L(G_{2})}$ share a derivable string.