Definition
A Context-Free Grammar (CFG) is a -tuple
– A finite set of variables.
– A finite set of terminals.
is not part of
– A finite set of rules. A rule is of the form
– A single start variable.
Observations
cannot be empty. It must contain the start variable
.
can be empty. In that case, all the rules will have
on the RHS.
can be empty. However, this will define the empty language.