Problem Solving in Automata, Languages, and Complexity

3.2 Examples of Context-Free Grammars 103

First, consider L 4. A string in L4 is of the form u~~+~P, where 3(5p+4) <
57-t < 4(5p+4), or 3p + 12/5 < n 5 4p + 16/5. Since n must be an integer,
the-above relation between p aid n is equivalent to

3p+3<n<4p+3. - -

This relation tells us that we can generate L4 by matching every five a’s with
three or four b’s, and then generating four extra a’s and three extra Vs. That
is, the grammar G4 = ({SJ, A}, {a, b), R4, S4) with rules

S4 + u4Ab3, A + u5Ab3 1 u5Ab4 1 E

generates the language L4.
Langauge L3 has a similar grammar. We note that 3(5p + 3) < - 5n < -
4(5p + 3) is equivalent to 3p + 2 < n < 4p + 2. So, in addition to the rules in
Go, we also need the rule 5’3 -+ u3Ab2to make up the extra u’s and b’s.
For language La, the relation 3(5p + 2) < 5n < 4(5p + 2) is simplified to
3p + 2 < n < 4p + 1. This relation creates &me problem with our approach.
Suppose thz we match 5p copies of u’s with j copies of b’s, with 3p < j < 4p.
Then, we cannot match the extra two u’s with any number of b’s: If we
generate extra two u’s with extra two b’s, then we may get as many as 4p+ 2
copies of b’s, which number is too large. On the other hand, if we generate
extra two u’s with only one extra b, then we may get as few as 3p + 1 copies
of b’s. To solve this problem, we change the above relation to

3(p - 1) + 5 < - n < - 4(p - 1) + 5.

Equivalently, strings in Lz are of the form u5(p--1)+7bq+5, with 3(p - 1) < - 4 < -
4(p - 1). Therefore, all we need to do is to generate extra seven u’s with extra
five b’s; or, equivalently, we need an extra rule 5’2 + u7Ab5. (Note: When
p = 0, there is no integer n satisfying the above inequality.)
Language L1 is similar to L2. The basic relation 3(5p+ 1) < - 5n < - 4(5p+ 1)
is equivalent to 3p + 1 < - n - < 4p. From that, we get

3(p - 1) + 4 < - n < - 4(p - 1) + 4.

So, in addition to the rules of Go, we need an extra rule S1 -+ u6Ab4.
Note that L is the union of languages Li, for 0 < i < 4. So, we can combine
the above rules together into a grammar for L: - -

S + u4Ab3 1 u3Ab2 1 u7Ab5 1 u6Ab4 1 A,

A + u5Ab3 I u5Ab4 I E. q

We solved the above problem by dividing the given language L into five
subproblems, finding a context-free grammar for each subproblem, and then
combining the five grammars into one. This technique is very useful for com-
plicated languages. The following theorem justifies this technique of combin-
ing simple grammars into a more complicated grammar.