Context-Free Grammars

Review: Grammars

Formal Notation

A grammar $G = (V, T, S, P)$ is said to be context-free if all productions in $P$ have the form

$$ A \rightarrow x, $$

where $A \in V$ and $x \in (V \cup T)^*$.

A language $L$ is said to be context-free if and only if there is a context-free grammar $G$ such that $L = L(G)$.

Leftmost and Rightmost Derivations

Leftmost derivation → in each step, the leftmost variable in the sentential form is replaced.

Rightmost derivation → in each step, the rightmost variable in the sentential form is replaced.

For example, the grammar with productions

$$ \begin{aligned} S & \rightarrow aAB, \\ A & \rightarrow bBb, \\ B & \rightarrow A | \lambda. \end{aligned} $$

has the following derivations of the string $abbbb$: