784
Modeling Arithmetic, Computation, and Languages
The productions of a grammar allow us to transform some words over V into
others; the productions can be called rewriting rules.
Definition GEnErAtions (DErivAtions) in A LAnGuAGE
Let G be a grammar, G = (V, V T , S, P), and let w 1 and w 2 be words over V.
Then w 1 directly generates (directly derives) w 2 , written w 1 1 w 2 , if a S b
is a production of G, w 1 contains an instance of a, and w 2 is obtained from w 1
by replacing that instance of a with b. If w 1 , w 2 , … , w n are words over V and
w 1 1 w 2 , w 2 1 w 3 , … , w n−1 1 w n , then w 1 generates (derives) w n , written
w 1 1 * w n . (By convention, w 1 1 * w 1 .)
example 49
Here is a very simple grammar: G = (V, V T , S, P) where V = 50, 1, S6,
V T = 50, 16, and P = 5S S 0S, S S 16.
example 50
In the grammar of Example 49, 00S 1 000S because the production S S 0S has
been used to replace the S in 00S with 0S. Also 00S 1 * 00000S.
PrACtiCe 62 Show that in the grammar of Example 49, 0S 1 * 00001.
■
Definition LAnGuAGE GEnErAtED By A GrAMMAr
Given a grammar G, the language L generated by G, sometimes denoted L(G),
is the set
L = 5w [ V T
* 0 S 1 * w6
In other words, L is the set of all strings of terminals generated from the start
symbol.
Notice that once a string w of terminals has been obtained, no productions can
be applied to w, and w cannot generate any other words.
The following procedure generates a list of the members of L: Begin with
the start symbol S and systematically apply some sequence of productions until
a string w 1 of terminals has been o btained; then w 1 [ L. Go back to S and repeat this procedure using a different sequence of productions to generate another
word w 2 [ L, and so forth. Actually, this procedure doesn’t quite work because we
might start on an infinite sequence of direct derivations that never leads to a string
of terminals and thus never contributes a word to our list. Instead, we need to run
a number of derivations from S simultaneously (parallel processing), checking on
each one after each step and adding the final word to the list of members of L for
any that terminate. That way we cannot get stuck waiting indefinitely while unable to do anything else.
ReminDeR
Productions may be used
in any order. The only
requirement is that the
left side of the production
must appear in the string
you are processing.
Modeling Arithmetic, Computation, and Languages
The productions of a grammar allow us to transform some words over V into
others; the productions can be called rewriting rules.
Definition GEnErAtions (DErivAtions) in A LAnGuAGE
Let G be a grammar, G = (V, V T , S, P), and let w 1 and w 2 be words over V.
Then w 1 directly generates (directly derives) w 2 , written w 1 1 w 2 , if a S b
is a production of G, w 1 contains an instance of a, and w 2 is obtained from w 1
by replacing that instance of a with b. If w 1 , w 2 , … , w n are words over V and
w 1 1 w 2 , w 2 1 w 3 , … , w n−1 1 w n , then w 1 generates (derives) w n , written
w 1 1 * w n . (By convention, w 1 1 * w 1 .)
example 49
Here is a very simple grammar: G = (V, V T , S, P) where V = 50, 1, S6,
V T = 50, 16, and P = 5S S 0S, S S 16.
example 50
In the grammar of Example 49, 00S 1 000S because the production S S 0S has
been used to replace the S in 00S with 0S. Also 00S 1 * 00000S.
PrACtiCe 62 Show that in the grammar of Example 49, 0S 1 * 00001.
■
Definition LAnGuAGE GEnErAtED By A GrAMMAr
Given a grammar G, the language L generated by G, sometimes denoted L(G),
is the set
L = 5w [ V T
* 0 S 1 * w6
In other words, L is the set of all strings of terminals generated from the start
symbol.
Notice that once a string w of terminals has been obtained, no productions can
be applied to w, and w cannot generate any other words.
The following procedure generates a list of the members of L: Begin with
the start symbol S and systematically apply some sequence of productions until
a string w 1 of terminals has been o btained; then w 1 [ L. Go back to S and repeat this procedure using a different sequence of productions to generate another
word w 2 [ L, and so forth. Actually, this procedure doesn’t quite work because we
might start on an infinite sequence of direct derivations that never leads to a string
of terminals and thus never contributes a word to our list. Instead, we need to run
a number of derivations from S simultaneously (parallel processing), checking on
each one after each step and adding the final word to the list of members of L for
any that terminate. That way we cannot get stuck waiting indefinitely while unable to do anything else.
ReminDeR
Productions may be used
in any order. The only
requirement is that the
left side of the production
must appear in the string
you are processing.