118 ~ Theory of Computer Science
3. Using 5 1 5 2 ~ b5 1 B, we add b to the left of 51 and variable B to the
right. Using B5 3 ~ 5 2 b5 3 , we add b to the right of 52'
4. 52 acts as a centre-marker.
5. We can add terminals only by using P 2 -P S '
6. P 6 -P 9 simply interchange symbols. They push A or B to the right. This
enables us to place A or B to the left of 53' (Only then we can apply
P 4 or P s .)
7. 5 1 5 2 ~ A, S3 ~ A are used to completely eliminate 5j, 5'J 53'
8. PIO, PlJ are used to push 52 to the left. This enables us to get 52 to
the right of 51 (so that we can apply Pd·
Let L = {x.x Ix E {a, b}*}. We first prove that L ~ L(G). Now, we have
5 => 5 1 S 2 S 3 => aSlAS3 => aSlS2aS3
(4.1)
or
S => SI5253 => bS jBS 3 => bS I S 2 b5 3
(4.2)
Let us start with xx with x E {ab}*. We can apply (4.1) or (4.2),
depending on the first symbol of x. If the first two symbols in x are ab (the
other cases are similar), we have
S :b a 5 1 S 2 aS3 => abS j Ba S3 => abSjaBS3 => abS 1 aS2 b5 3 => ab5 1 5 2 abS 3
Repeating the construction for every symbol in x, we get XSlS2xS3' On
application of P 12 and P 13 , we get
5 :b XSlS2XS3 :b xAxA = xx
Thus, L ~ L(G).
To prove that L(G) ~ L, we note that the first three steps in any derivation
of L(G) are given by (4.1) or (4.2). Thus in any derivation (except S ~ A), we
get aSjS2a53 or bS 1 5 2 bS 3 as a sentential form.
We can discuss the possible ways of reducing aS I S::a5 3 (the other case is
similar) to a terminal string. The first production that we can apply to aS152aS3
is one of SIS:: ~ A. 53 ~ A S1S2 ~ aSIA, S1S2 ~ bS 1 B.
Case 1 We apply 5 I S:: ~ A to aSlS::aS3' In this case we get aAa5 3 . As the
productions involving S3 on the left are P 4 , P s or P D , we have to apply only
S3 ~ l\. to aa5 3 and get aa E L.
Case 2 We apply 53 ~ A to a5152aS3' In this case we get a5 1 S 2 aA. If we
apply S1S2 ~ A, we get aAaA = aa E L; or we can apply S1S2 ~ aSIA to
aSIS2a to get aaSIAa. In the latter case, we can apply only Aa ~ aA to aaSjAa.
The resulting string is aaSlaA which cannot be reduced further.
From Cases 1 and 2 we see that either we have to apply both PI:: and P 13
or neither of them.
Case 3 In this case we apply 5 1 S 2 ~ aSjA or 5 j 5 2 ~ bS 1 B. If we apply
5 j S 2 ~ a5 jA to as\S2aS3' we get aaSjAaS3' By the nature of productions we
have to follow only aaSjAa5 3 => aaSjaAS 3 => a2S1aS2aS3 => a2SjS2a2S3' If
3. Using 5 1 5 2 ~ b5 1 B, we add b to the left of 51 and variable B to the
right. Using B5 3 ~ 5 2 b5 3 , we add b to the right of 52'
4. 52 acts as a centre-marker.
5. We can add terminals only by using P 2 -P S '
6. P 6 -P 9 simply interchange symbols. They push A or B to the right. This
enables us to place A or B to the left of 53' (Only then we can apply
P 4 or P s .)
7. 5 1 5 2 ~ A, S3 ~ A are used to completely eliminate 5j, 5'J 53'
8. PIO, PlJ are used to push 52 to the left. This enables us to get 52 to
the right of 51 (so that we can apply Pd·
Let L = {x.x Ix E {a, b}*}. We first prove that L ~ L(G). Now, we have
5 => 5 1 S 2 S 3 => aSlAS3 => aSlS2aS3
(4.1)
or
S => SI5253 => bS jBS 3 => bS I S 2 b5 3
(4.2)
Let us start with xx with x E {ab}*. We can apply (4.1) or (4.2),
depending on the first symbol of x. If the first two symbols in x are ab (the
other cases are similar), we have
S :b a 5 1 S 2 aS3 => abS j Ba S3 => abSjaBS3 => abS 1 aS2 b5 3 => ab5 1 5 2 abS 3
Repeating the construction for every symbol in x, we get XSlS2xS3' On
application of P 12 and P 13 , we get
5 :b XSlS2XS3 :b xAxA = xx
Thus, L ~ L(G).
To prove that L(G) ~ L, we note that the first three steps in any derivation
of L(G) are given by (4.1) or (4.2). Thus in any derivation (except S ~ A), we
get aSjS2a53 or bS 1 5 2 bS 3 as a sentential form.
We can discuss the possible ways of reducing aS I S::a5 3 (the other case is
similar) to a terminal string. The first production that we can apply to aS152aS3
is one of SIS:: ~ A. 53 ~ A S1S2 ~ aSIA, S1S2 ~ bS 1 B.
Case 1 We apply 5 I S:: ~ A to aSlS::aS3' In this case we get aAa5 3 . As the
productions involving S3 on the left are P 4 , P s or P D , we have to apply only
S3 ~ l\. to aa5 3 and get aa E L.
Case 2 We apply 53 ~ A to a5152aS3' In this case we get a5 1 S 2 aA. If we
apply S1S2 ~ A, we get aAaA = aa E L; or we can apply S1S2 ~ aSIA to
aSIS2a to get aaSIAa. In the latter case, we can apply only Aa ~ aA to aaSjAa.
The resulting string is aaSlaA which cannot be reduced further.
From Cases 1 and 2 we see that either we have to apply both PI:: and P 13
or neither of them.
Case 3 In this case we apply 5 1 S 2 ~ aSjA or 5 j 5 2 ~ bS 1 B. If we apply
5 j S 2 ~ a5 jA to as\S2aS3' we get aaSjAaS3' By the nature of productions we
have to follow only aaSjAa5 3 => aaSjaAS 3 => a2S1aS2aS3 => a2SjS2a2S3' If