Section 9.5 Formal Languages
783
Before we give a formal definition of what constitutes a grammar, let’s look
again at why, “The walrus talks loudly,” seems to be an acceptable sentence by
seeing how it could be generated. Starting from the notion of sentence, we would
agree that one legitimate form for a sentence is a noun phrase followed by a verb
phrase. Symbolically,
sentence S noun-phrase verb-phrase
A legitimate form of noun phrase is an article followed by a noun,
noun-phrase S article noun
and a legitimate form of verb phrase is a verb followed by an adverb,
verb-phrase S verb adverb
We would also agree with the substitutions
article S the
noun S walrus
verb S talks
adverb S loudly
Thus we can generate the sentence, “The walrus talks loudly,” by making successive substitutions:
sentence 1 noun-phrase verb-phrase
1 article noun verb-phrase
1 the noun verb-phrase
1 the walrus verb-phrase
1 the walrus verb adverb
1 the walrus talks adverb
1 the walrus talks loudly
The foregoing boldface terms are those for which further substitutions can be
made. The nonboldface terms stop or terminate the substitution process. These
ideas are incorporated in the next definition.
Definition PhrAsE-struCturE (tyPE 0) GrAMMAr
A phrase-structure grammar (type 0 grammar) G is a 4-tuple, G = (V, V T , S, P),
where
V = vocabulary
V T = nonempty subset of V called the set of terminals
S = element of V – V T called the start symbol
P = finite set of productions of the form a S b where a is a word over V
containing at least one nonterminal symbol and b is a word over V