• V is the set of variables, or nonterminals.
      • Typically in upper case
    • Σ is the set of terminal symbols.
      • Typically in lower case
    • R is the set of production rules.
      • X -> Y1..Yn
      • X is non terminal
      • Y can be NT, T, epsilon
    • S is the start symbol.
    • Example:
      • S -> (S)
      • S -> epsilon
  • S → aSa | bSb | a | b | ε
  • N → ε
PalindromeDerivation
abbaS ⇒ NT ⇒ aT ⇒ ab ⇒ abba
abaS ⇒ NT ⇒ aT ⇒ ab ⇒ aba
bS ⇒ NT ⇒ b ⇒ b
aaS ⇒ NT ⇒ aa
  • Derive
  • Yields