Problem Solving in Automata, Languages, and Complexity

106 CONTEXT-FREE LANGUAGES

and Gy = (0, {O,l}Ry,A), with

Then, X = L(Gx) and Y = L(Gy). C om b ining them together, we get the

grammar G = ({S, A, B}, (0, l}, R, S) for language L, where

R=RxuRyu{S+AIBIABIBA}. cl

Solution 2. In Solution 1, we have constructed grammars Gx and Gy for sets

X and Y, respectively. Now, define a new grammar G’ = ({S}, { 0, l}, R’, S),

with

R = {S + 0 I 1 I01 I lo}.

Then, using the substitution f(0) = X and f(1) = Y, we have f(L(G’)) = L,
and the construction of Theorem 3.18 gives us the same grammar G for L as
the one in Solution 1.^0

• Example 3.21 For i > - 1, denote by bi the binary representation of integer
  i (with no leading zeroes). Find a context-free grammar generating

L = {O,l, #} - {bl#bz#. l #b, 1 n > - 1).

Solution. Note that a string g = al#cza#.. #a,, with each uj E (0, l},
belongs to the set {bl#bz# l. l #b, I n > 1) if and only if al = 1, and for
every j, 1 < j 5 n- 1, aj#aj+r is of the form bi#bi+l for some integer i > 1.
In other words, a string z E {O,l, #}*

• is in L if and only if it satisfies one of
  the following conditions:
  (1) [d: = y] or [z has a prefix y#] for some y E (0, l} - { 1).
  (2) [x = y#z] or [Z has a prefix y#z#] or [Z has a substring #y#~#] or [a:
  has a suffix #y#x] for some y, x E (0, l} such that y#x # ba#bi+l for
  any integer i 2 1.
  The above conditions (1) and (2) may be expressed by the regular expres-
  sion notation as follows:

L = Ll(#(O + I)*)* u ((0 + l)*#)*b(#(o + I)*)*,

where

Ll = {Y fs -to, 1)’ I Y # 11,

L2 = {y#z I y, x E {O,l}*, y#x # bi#bi+l for any i 2 1).

The language L1 is regular: L1 = E + (0 + 10 + ll)(O + l)*, and it can be

generated by the following rules, starting with S1:

S1 -+ E 1 OA 1 1OA I OlA, A ---+ E ( OA I 1A.

To find a context-free grammar for L 2, let us first analyze how the string

b i+l is related to bi: