Formal Grammar

Grammar is formally defined as a tuple:

$G=(V,T,S,P)$

• $V$ are variable symbols to be used in the language (they can’t be in a string, because they’re placeholders)
• $T$ are terminal symbols to be used in the language.
• $S$ is the start variable
• $P$ is the production rules

Notation for production rules:

• $w\Rightarrow z$: w derives z
• $w\stackrel{\ast }{\Rightarrow }z$: w derives z in zero or more steps
• $w\stackrel{+}{\Rightarrow }z$: w derives z in one or more steps

Normal Forms §

• Greibach Normal Form
• Chompsky Normal Form