Grammar is formally defined as a tuple:

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

Notation for production rules:

  • : w derives z
  • : w derives z in zero or more steps
  • : w derives z in one or more steps

Normal Forms