This is written as
We say that w derives z or that z is derived from w. Successive strings are
derived by applying the productions of the grammar in arbitrary order. A
production can be used whenever it is applicable, and it can be applied as often
as desired. If
we say that w 1 derives w n and write
The * indicates that an unspecified number of steps (including zero) can be taken
to derive w n from w 1 .
By applying the production rules in a different order, a given grammar can
normally generate many strings. The set of all such terminal strings is the
language defined or generated by the grammar.
Definition 1.2
Let G = (V, T, S, P) be a grammar. Then the set
is the language generated by G.
If w ∈ L (G), then the sequence
is a derivation of the sentence w. The strings S, w 1 , w 2 ,…, w n , which contain
variables as well as terminals, are called sentential forms of the derivation.
Example 1.11
We say that w derives z or that z is derived from w. Successive strings are
derived by applying the productions of the grammar in arbitrary order. A
production can be used whenever it is applicable, and it can be applied as often
as desired. If
we say that w 1 derives w n and write
The * indicates that an unspecified number of steps (including zero) can be taken
to derive w n from w 1 .
By applying the production rules in a different order, a given grammar can
normally generate many strings. The set of all such terminal strings is the
language defined or generated by the grammar.
Definition 1.2
Let G = (V, T, S, P) be a grammar. Then the set
is the language generated by G.
If w ∈ L (G), then the sequence
is a derivation of the sentence w. The strings S, w 1 , w 2 ,…, w n , which contain
variables as well as terminals, are called sentential forms of the derivation.
Example 1.11