-
- 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
- V is the set of variables, or nonterminals.
- S → aSa | bSb | a | b | ε
- N → ε
| Palindrome | Derivation |
|---|---|
| abba | S ⇒ NT ⇒ aT ⇒ ab ⇒ abba |
| aba | S ⇒ NT ⇒ aT ⇒ ab ⇒ aba |
| b | S ⇒ NT ⇒ b ⇒ b |
| aa | S ⇒ NT ⇒ aa |
- Derive
- Yields