786
Modeling Arithmetic, Computation, and Languages
S 1 *
1
a
n−1
S(BC )
n−1
1 2 a
n
(BC )
n
1 *
3
a
n
B
n
C
n
1 4 a
n
bB
n−1
C
n
1 *
5
a
n
b
n
C
n
1 6 a
n
b
n
cC
n−1
1 *
7
a
n
b
n
c
n
We must also show that L(G) # L, which involves arguing that some productions
must be used before others and that the general derivation shown above is the only
sort that will lead to a string of terminals.
In trying to invent a grammar to generate the L of Example 52, we might
first try to use productions of the form B S b and C S c instead of productions
4 through 7. Then we would indeed have L # L(G), but L(G) would also include
words such as a
n
(bc)
n
.
Formal languages were developed in the 1950s by linguist Noam Chomsky
in an attempt to model natural languages, such as English, with an eye toward
automatic translation. However, since a natural language already exists and is
quite complex, defining a formal grammar to generate a natural language is very
difficult. Attempts to do this for English have been only partially successful.
ReminDeR
“Throwing in” productions to get the language
L you want often means
that you generate more
than L. The productions
must generate exactly the
strings in L.
example 53
We can describe a formal grammar that will generate a very restricted class of
English sentences. The terminals in the grammar are the words “the,” “a,” “river,”
“walrus,” “talks,” “flows,” “loudly,” and “swiftly,” and the nonterminals are the
words sentence, noun-phrase, verb-phrase, article, noun, verb, and adverb.
The start symbol is sentence and the productions are
sentence S noun-phrase verb-phrase
noun-phrase S article noun
verb-phrase S verb adverb
article S the
article S a
noun S river
noun S walrus
verb S talks
verb S flows
adverb S loudly
adverb S swiftly
We know how to derive, “The walrus talks loudly,” in this grammar. Here is a
derivation of, “A river flows swiftly”:
Modeling Arithmetic, Computation, and Languages
S 1 *
1
a
n−1
S(BC )
n−1
1 2 a
n
(BC )
n
1 *
3
a
n
B
n
C
n
1 4 a
n
bB
n−1
C
n
1 *
5
a
n
b
n
C
n
1 6 a
n
b
n
cC
n−1
1 *
7
a
n
b
n
c
n
We must also show that L(G) # L, which involves arguing that some productions
must be used before others and that the general derivation shown above is the only
sort that will lead to a string of terminals.
In trying to invent a grammar to generate the L of Example 52, we might
first try to use productions of the form B S b and C S c instead of productions
4 through 7. Then we would indeed have L # L(G), but L(G) would also include
words such as a
n
(bc)
n
.
Formal languages were developed in the 1950s by linguist Noam Chomsky
in an attempt to model natural languages, such as English, with an eye toward
automatic translation. However, since a natural language already exists and is
quite complex, defining a formal grammar to generate a natural language is very
difficult. Attempts to do this for English have been only partially successful.
ReminDeR
“Throwing in” productions to get the language
L you want often means
that you generate more
than L. The productions
must generate exactly the
strings in L.
example 53
We can describe a formal grammar that will generate a very restricted class of
English sentences. The terminals in the grammar are the words “the,” “a,” “river,”
“walrus,” “talks,” “flows,” “loudly,” and “swiftly,” and the nonterminals are the
words sentence, noun-phrase, verb-phrase, article, noun, verb, and adverb.
The start symbol is sentence and the productions are
sentence S noun-phrase verb-phrase
noun-phrase S article noun
verb-phrase S verb adverb
article S the
article S a
noun S river
noun S walrus
verb S talks
verb S flows
adverb S loudly
adverb S swiftly
We know how to derive, “The walrus talks loudly,” in this grammar. Here is a
derivation of, “A river flows swiftly”: