Chapter 4: Formal Languages ~ 119
we apply 5)5 2 ---,) b5\B, we get ab5 1 5 2 ab5 3 . Thus the effect of applying
5)5 2 ---,) a5)A is to add a to the left of 5 1 5 2 and 53'
If we apply 5)S2 ---,) A, S3 ---,) A (By Cases 1 and 2 we have to apply both)
we get abab.E L. Otherwise, by application of P2 or P 3 , we add the same
terminal symbol to the left of SIS2 and S3' The resulting string is of the form
x51S2XS3' Ultimately, we have to apply P)2 and P i3 and get xAxA =xx E L. So
L(G) ~ L. Hence, L(G) =L.
EXAMPLE 4.1 3
Let G = ({S, AI- AJ, {a, b}, P, S), where P consists of
5 ---,) aA 1 A 2 a, A) ---,) baA I A 2 b, A 2 ---,) Alab, aA I ---,) baa, bA 2 b ---,) abab
Test whether w =baabbabaaabbaba
is in L(G).
Solution
We have to start with an 5-production. At every stage we apply a suitable
production which is likely to derive w. In this example, we underline the
substring to be replaced by the use of a production.
S::::} aA I A 2 a
::::} baa A 2 a
::::} baabbaa A 2 baba
::::} baabba aA) abbaba
::::} baabbabaaabbaba = w
Therefore.
11' E L(G)
EXAM PLE 4.14
If the grammar G is given by the productions S ---,) aSa I bSb i aa i bb I A,
show that (i) L(G) has no strings of odd length, (ii) any string in L(G) is of
length 2n, n 2: 0, and (iii) the number of strings of length 2n is 2".
Solution
0- application of any production (except S ---,) A), a variable is replaced by
two terminals and at the most one variable. So, every step in any derivation
increases the number of terminals by 2 except that involving 5 ---,) A. Thus,
we have proved (i) and (ii).