Problem Solving in Automata, Languages, and Complexity

102 CONTEXT-FREE LANGUAGES

Solution. First, let us consider the simpler language L1 = { a”b”cp 1 m+ 272 =
p). Based on the idea of the last example, we can easily get the following
grammar for it:
5’ + aSc 1 A, A + bAcc 1 F.

Next, we modify this grammar to allow the case m. + 272 > JX This can
happen if we have (i) at least one extra a, or (ii) at least one extra b, or (iii)
at least one extra b together with one extra c. These extra symbols may occur
in both matching stages of the derivation. Thus, we can add rules S -+ US,
A + bA and A + bAc to the grammar for L1. That is, the grammar for
language L is as follows:

S + aSc 1 aS 1 A, A + bAcc I bAc I bA I E. cl

* Example 3.16 Find a context-free grammar that generates the language

L = {ambn I3m < - 5n < - 4m).

Solution. First, we consider a simpler language: Lo = {ambn I 3m < 5n < -

4m,m E 0 (mod 5)). For any string a ‘J’bn in Lo, we must have 15~ 1 5n <

2Op, or, 3p < - n - < 4~. Thus, we may rewrite Lo as

LO = {a5pb3p+k IO < - k 5 p}.

From this expression, it is easy to see that Lo is generated by the grammar
Go = ({A}, {a, b}, Ro, A) with the following rules:

A + a5Ab3 I a5Ab4 I E.

Intuitively, this grammar matches every five u’s with either three b’s or four

b’s. Therefore, the total number of b’s is between 3/5 and 4/5 of the number

of a’s. More formally, we note that if a derivation A 3 a5Pbn applies the

rule A + a5Ab4 for k times, the rule A + a5Ab3 for p - k times, and the

rule A -+ E at the end, then we must have n = 3p + k. Thus, every string in

Lo can be generated by the grammar Go. Conversely, it is obvious that these

are the only possible derivations from symbol A. Thus, we have proved that

L(Go) = LO.

The above idea of matching every five a’s with either three or four b’s is

critical in this problem. We can actually apply this to other strings in L. Let

us define, for each i = 1,2,3,4, a language

Li = {a”bn I 3m < - 5n - < 4m, m E i (mod 5)}.

For each Li, 1 < i < 4, we can use this matching idea to construct a grammar
forit. - -