Section 9.5 Formal Languages
785
PrACtiCe 63 Describe the language generated by the grammar G of Example 49.
■
Languages derived from grammars such as we have defined are called formal
languages. If the grammar is defined first, the language will follow as an outcome
of the definition. Alternatively, the language, as a well-defined set of strings, may
be given first, and we then seek a grammar that generates it.
example 51
Let L be the set of all nonempty strings consisting of an even number of 1s. Then
L is generated by the grammar G = (V, V T , S, P) where V = 51, S6, V T = 516,
and P = 5S S SS, S S 116. A language can be generated by more than one
grammar. L is also generated by the grammar G′ = (V′, V′ T , S′, P′) where
V′ = 51, S6, V′ T = 516, and P′ = 5S S 1S1, S S 116.
PrACtiCe 64
a. Find a grammar that generates the language L = 50
n
10
n
0 n ≥ 06.
b. Find a grammar that generates the language L = 50
n
10
n
0 n ≥ 16.
■
Trying to describe concisely the language generated by a given grammar and
defining a grammar to generate a given language can both be quite difficult tasks.
We’ll look at another example where the grammar is a bit more complicated than
any we’ve seen so far. Don’t worry about how you might think up this grammar;
just convince yourself that it works.
example 52
Let L = 5a
n
b
n
c
n
0 n ≥ 16. A grammar generating L is G = (V, V T , S, P) where
V = 5a, b, c, S, B, C6, V T = 5a, b, c6, and P consists of the following productions:
1. S S aSBC
3. CB S BC
5. bB S bb
7. cC S cc
2. S S aBC
4. aB S ab
6. bC S bc
It is fairly easy to see how to generate any particular member of L using these productions. Thus, a derivation of the string a
2
b
2
c
2
is
S 1 aSBC
1 aaBCBC
1 aaBBCC
1 aabBCC
1 aabbCC
1 aabbcC
1 aabbcc
In general, L # L(G) where the outline of a derivation for any a
n
b
n
c
n
is given below; the numbers refer to the productions used.