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

CHAP. 12] LANGUAGES, AUTOMATA, GRAMMARS 311

EXAMPLE 12.9 The following defines a grammarGwithSas the start symbol:

V={A, B, S, a, b},T={a, b},P={S

1

→AB, A

2

→Aa, B

3

→Bb, A

4

→a, B

5

→b}

The productions may be abbreviated as follows:S→AB,A→(Aa, a),B→(Bb, b)

LanguageL(G)of a GrammarG

Supposewandw′are words over the vocabulary setVof a grammarG. We write

w⇒w′

ifw′can be obtained fromwby using one of the productions; that is, if there exists wordsuandvsuch that
w=uαvandw′=uβ vand there is a productionα→β. Furthermore, we write

w⇒⇒w′ or w

∗

⇒w′

ifw′can be obtained fromwusing a finite number of productions.
Now letGbe a grammar with terminal setT. The language ofG, denoted byL(G), consists of all words in
Tthat can be obtained from the start symbolSby the above process; that is,

L(G)={w∈T∗|S⇒⇒w}

EXAMPLE 12.10 Consider the grammarGin Example 12.9. Observe thatw=a^2 b^4 can be obtained from
the start symbolSas follows:

S⇒AB⇒AaB⇒aaB⇒aaBb⇒aaBbb⇒aaBbbb⇒aabbbb=a^2 b^4

Here we used the productions 1, 2, 4, 3, 3, 3, 5, respectively. Thus we can writeS⇒⇒a^2 b^4. Hencew=a^2 b^4
belongs toL(G). More generally, the production sequence:

1 , 2 (rtimes), 4 , 3 (stimes), 5

will produce the wordw=arabsbwhererandsare nonnegative integers. On the other hand, no sequence of
productions can produce anaafter ab. Accordingly,

L(G)={ambn|mandnare positive integers}

That is, the languageL(G)of the grammarGconsists of all words which begin with one or morea’s followed
by one or moreb’s.

EXAMPLE 12.11 Find the languageL(G)over{a, b, c}generated by the grammarG:

S→aSb, aS→Aa, Aab→c

First we must apply the first production one or more times to obtain the wordw=anSbnwheren>0. To
eliminateS, we must apply the second production to obtain the wordw′=amAabbmwherem=n− 1 ≥0.
Now we can only apply the third production to finally obtain the wordw′=amcbmwherem≥0. Accordingly,

L(G)={amcbm|mnonnegative}

That is,L(G)consists of all words with the same nonnegative number ofa’s andb’s separated byac.