title: "Context-Free Grammar"

Context-Free Grammar

Definition. A context-free grammar is a four-tuple $G = (V, \Sigma, R, S)$ where $V$ is a finite set of variables, $\Sigma$ is a finite set of terminals disjoint from $V$, $R$ is a finite set of rules of the form $A \to w$ with $A \in V$ and $w \in (V \cup \Sigma)^*$, and $S \in V$ is the start variable.

A grammar generates strings rather than recognizing them: begin with $S$ and repeatedly replace a variable by the right-hand side of one of its rules, until only terminals remain. The name records the restriction that a rule's left side is a single variable, so what a variable may become never depends on what surrounds it. Defined in Lecture 5, where grammars are proved equivalent to the pushdown automaton. A grammar may be ambiguous even when the language it generates has an unambiguous grammar.