Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

310 LANGUAGES, AUTOMATA, GRAMMARS [CHAP. 12

12.6Grammars

Figure 12-5 shows the grammatical construction of a specific sentence. Observe that there are:

(1) various variables, e.g., (sentence), (noun phrase),···;

(2) various terminal words, e.g., “The”, “boy,”···;

(3) a beginning variable (sentence);

(4) various substitutions or productions, e.g.

〈sentence〉→〈noun phrase〉〈verb phrase〉

〈object phrase〉→〈article〉〈noun〉

〈noun〉→apple

The final sentence only contains terminals, although both variables and terminals appear in its construction by the
productions. This intuitive description is given in order to motivate the following definition of a grammar and
the language it generates.

Fig. 12-5

Definition 12.4:Aphrase structure grammaror, simply, agrammarGconsists of four parts:

(1) A finite set (vocabulary)V.

(2) A subsetTofVwhose elements are calledterminals; the elements ofN=V\Tare callednon-terminals

orvariables.

(3) A nonterminal symbolScalled thestartsymbol.

(4) A finite setPof productions. (A production is an ordered pair (α,β), usually writtenα→β, whereαand

βare words inV, and the production must contain at least one nonterminal on its left sideα.)

Such a grammarGis denoted byG=G(V,T,S,P)when we want to indicate its four parts.

The following notation, unless otherwise stated or implied, will be used for our grammars. Terminals will
be denoted by italic lower case Latin letters,a, b, c,···, and nonterminals will be denoted by italic capital Latin
letters,A, B, C,···, withSas the start symbol. Also, Greek letters,α, β,···, will denote words inV, that is,
words in terminals and nonterminals. Furthermore, we will write

α→(β 1 ,β 2 ,···,βk) instead of α→β 1 ,α→β 2 ,···,α→βk

Remark: Frequently, we will define a grammarGby only giving its productions, assuming implicitly thatS
is the start symbol and that the terminals and nonterminals ofGare only those appearing in the productions.