Context-Free Grammar

Context-free grammar (CFG) are a recursive set of rules that generate a language, similar to their weaker counterpart, regular expressions. Unlike regular expressions, they are capable of generating non-regular languages, such as the ubiquitous $L=\{0^n{1}^n|n\in \mathbb{N}\}$ language.

CFGs are used in many markdown file formats, such as JSON and XML. In fact, the definition of regular expression is actually a CFG. The ability to recursively define a set of rules gives CFGs much more power than regular expressions.

Definition §

Context-free Grammar (CFG) ^definition

A context-free grammar $G$ is defined as a 4-tuple:

$$G=(\Sigma ,V,R,S)$$

• $\Sigma$ = An alphabet. In the context of CFGs, this is also referred to a set of terminals (since they do not recursively depend on anything, think of base cases in recursion
• $V$ = A finite set of variables (also called non-terminals, for obvious reasons). These act like recursive expressions.
• $R:V\to (V\cup \Sigma {)}^{\ast }$ = A finite set of production rules, written in the form $R(X,a)$. $R$ takes in a variable $X$ and returns a string containing terminals (belonging to $\Sigma$) and/or more variables (belonging to $V$).
  • $R$ can (and usually is) self-referential. A production rule $X\to X\circ a$ is valid.
  • Another common notation used is that when we use a production rule, $A\to y$ on a string $xAz$ to get $xyz$, we can write it as $xAz⟹xyz$:
• $S$ = The start variable

Note the similarities between production rules and logical substitution, with the only difference being that a logical substitution applies to the entire formula, replacing every instance, while a production rule replaces once instance at a time.

Derivation ^definition-derivation

Let $p$ and $c$ be two strings containing variables and/or terminals ($x,z\in (V\cup \Sigma {)}^{\ast }$). Also let $y_1,y_2,\dots ,y_k$ be similar strings containing variables and/or terminals. Then $p$ derives $c$ iff:

$$x\Rightarrow y_1\Rightarrow y_2\Rightarrow \cdots \Rightarrow y_k\Rightarrow$$

z

$$Thisisnotatedas:$$

x \Rightarrow^* z

* We say that $c$ is *derived from* $p$ * The derivation must be *finite* (as in $y_{k}$ is defined for some natural number) * Note the similarities to [resolution proofs](Resolution%20Proof.md)

• Strings in $(V\cup \Sigma {)}^{\ast }$ are known to be in sentential form (because they still need to recursed further, so not quite a sentence)
• A string in ${\Sigma }^{\ast }$ is a sentence (since it contains all terminals).

Language of a CFG ^definition-language

The language, $L$ generated by a CFG, $G$ (with start variable $S$) is given by:

$$L(G)=\{x|S{\Rightarrow }^{\ast }x\}$$

Ambiguity §

Ambiguity

A string $w$ is ambiguous with respect to a grammar, $G$, iff $G$ has more than one parse tree for $w$. That is, the parse tree for $w$ is not unique.

A grammar, $G$ is ambiguous if it contains at least one ambiguous string.

Backus–Naur Form (Shorthand Notation) §

A way to simplify writing the production rules, $R$, is by using the Backus-Naur Form, where:

$$R=\{S\to a,S\to S,S\to S\circ a\}$$

Becomes:

$$S\to a|S|S\circ a$$

A further simplification is to only define the production rules for a CFG, because anything on the left of the arrow must be a variable, and anything on the right (that isn’t already a variable), must belong to the alphabet.

For example:

$$X\to a|x|X\circ bx\to a|b|c$$

results in:

• $\Sigma =\{a,b,c\}$
• $V=(X,x)$

Generating A Language §

Generating a language from a CFG is very straightforward. Let $w$ be a (initially empty) string and $G=(\Sigma ,V,R,S)$

1. $w=S$, set the string to be the start variable of $G$
2. While $w$ contains at least one variable:
   1. Pick any one production rule from $R$ and apply it to one instance/occurrence of the variable. If $w$ contains multiple variable, pick one. For example, if a variable $A$ is encountered and $R$ contains $A\to s$, replace one occurrence of $A$ in $w$ with $s$.
3. When $w$ has no more variables (contains only terminals), stop.

Applying every permutation production rules across every variable occurrence will generate a langage $L$ from $G$.

Parse Tree §

Context-free grammars can easily be depicted by an expression tree, due to its recursive nature.

The expression tree is a rooted tree where

• An expression tree for a CFG must have the start variable, $S$ as the root.

• Each node is either a terminal or variable.
• Each non-leaf node and its children is associated with a production rule. In particular, if the production rule is A→wA→w then AA is the label of the non-leaf node and the symbols in ww are the labels of the children, in left to right order.
• Each leaf is a terminal. The concatenation of the leaf labels, in left to right order, gives the string $w$

For example, take the CFG defining arithmetic expressions. The expression tree (for a given expression) would be of the form: %%🖋 Edit in Excalidraw, and the dark exported image%%

Examples §

E1: Arithmetic BODMAS as a CFG ^e1

Any arithmetic expression can easily be expressed as a CFG:

$$(3+9)\times 18-3$$

• $\Sigma =\{0,1,2,3,4,5,6,7,9,+,-,\times ,÷,(,)\}$
  • $\Sigma$ needs to also include our operators and brackets, since being a language, we have no notion of ‘evaluating’ an expression (no semantics), but we have a very strict syntax.
• $V=\{\text{op},\text{expr}\}$ : For defined arthmatic operators versus expressions

R:\quad\text{op} \to + \ \vert \ - \ \vert \ \times \ \vert \ \div \ \vert \ \quad\quad \text{expr} \to 0 \ \vert \ 1 \ \vert \ \dots \ \vert \ 9 \ \vert \ \text{(expr)}\ \vert \ \text{expr op expr}

* $S = \text{expr}$

E2: CFG for equal number of 0s and 1s in order

The context-free language given below can be expressed as a CFG:

$$L=\{0^n{1}^n|n\in {\mathbb{N}}_0\}$$

We can express this using only the production rules:

$$R:S\to 0\circ S\circ 1|ϵ$$