Terminology of Grammars
- A grammar is a 4-tuple G = (N, E, P, S).
- N is a finite set of non-terminal symbols.
- E is a finite set of terminal symbols.
- P is a finite subset of
(N + E)*N(N + E)* x (N + E)*
- Elements (a, b) in P will be written
a -> b and are called productions.
- S is an element of N called the start symbol.
S -> 0 A 1
0 A -> 0 0 A 1
A -> e
The non-terminals are A and S, and the terminals are
0 and 1. The start symbol is S. e
is a special symbol denoting the empty string.