Chapter 4: Formal Languages ~ 115
EXAMPLE 4.9
Find a grammar generating {a'b"e"! 11 ~ L j ~ O}.
Solution
Let G = ({5, A}, {a. b, e}, P, 5). where P consists of 5 ~ as, 5 ~ A.
A ~ bAe ! be. As in the previous example, we can prove that G is the required
grammar.
EXAMPLE 4.10
Let G =({5. Ad. {O. L 2}. p. 5), where P consists of 5 ~ 05A[2. 5 ~ 012,
2A 1 ~ A]2. lA] ~ 11. Show that
L(G) = {0"1"2" I 11 ~ I}
Solution
As 5 ~ 012 is a production, we have 5 ::::} 012, i.e. 012 E L(G).
Also.
5 :b 0"-1 5(A 12t-1
::::} 0"12(A 1 2)"-]
::::} 0"IA{'-12"
~ 0"1"2"
Therefore.
by applying 5 ~ 05A]2 (11 - 1) times
by applying 5 ~ 012
by applying 2A] ~ A l 2 several times
by applying lA I ~ 11
(11 - 1) times
0"1"2" E UG)
for all 11 ~ 1
To prove that L( G) <:;::;; {0"1"2"1 11 ~ I}, \ve proceed as follows: If the first
production that we apply is 5 ~ 012, we get 012. Otherwise we have to apply
5 ~ 05A l L once or several times to get 0"-]S(A 1 2t- 1 . To eliminate 5, we have
to apply 5 ~ 012. Thus we arrive at a sentential form 0" 12(A] 2),,-1. To
eliminate the variable A 1 • we have to apply 2A 1 ~ A l 2 or lA] ~ 11. Now.
LA 1 ~ A12 interchanges 2 and A l' Only lA 1 ~ 11 eliminates A 1. The sentential
form we have obtained is O"12A}2A 1 2 ... A 1 2. If we use lA} ~ 11 before
taking all 2' s to the right. \ve wilJ get 12 in the middle of the string. The A. i • s
appearing subsequently cannot be eliminated. So we have to bring all 2's to the
right by applying 24] ~ A]2 several times. Then we can apply 1/\1 ~ 11
repeatedly and get 0" 1" 2" (as derived in the first part of the proof). Thus.
L(G) <:;::;; {0"1"2"111 ~ l}
This shows that
L( G) = {O" 1" 2" In 2: I}
In the next example we constmct a grammar generating
{a"ll'e" i' l1 ~ I}