134 ~ Theory of Computer Science
12. {d'b"cflll n, m 2: 1} is
(a) regular
(b) context-free but not regular
(c) context-sensitive but not context-free
(d) none of these.
State whether the following Statements 13-20 are true or false:
13. In a grammar G = (\!,y, 2:, P, S), \!,V and 2: are finite but P can be
infinite.
14. Two grammars of different types can generate the same language.
15. If G = (VV, 2:. P, S) and P "j:. 0, then L(G) "j:. 0.
16. If a grammar G has three productions, i.e. S ~ AA, A -) aa, A -~
bb, then L(G) is finite.
17. If L I = {d'blllim, n 2: 1} and L 2 = {bflld'lm, p 2: 1}, then L I n L 2 =
{a"b"c/l11 2: I}.
18. If a grammar G has productions S -~ as IbS Ia, then L(G) =the set of
all strings over {a, b} ending in a.
19. The language {a"bc" In 2: 1} is regular.
20. If the productions of G are S ~ as ISb Ia I17, then abab E L(G).
EXERCISES
4.1 Find the language generated by the following grammars:
(a) S ~ OSll OA1, A ~ IA 11
(b) S ~ OSII OA I0 IIIB 11, A ~ OA I0, B ~ lB 11
(c) S ~ OSBA lOlA, AB ~ BA, IB ~ 11, lA ~ 10, OA ~ 00
(d) S ~ OSlIOAl, A ~ lAOllO
(e) S ~ OA lIS 1011, A ~ lA lIS 11
4.2 Construct the grammar, accepting each of the following sets:
(a) The set of all strings over {O, I} consisting of an equal number of
O's and l's.
(b) {O"IIIlOIllI"!m, n 2: I}
(c) {Oil 1 211 In 2: l}
(d) {Oil 111 In 2: I} u {III/Oil/1m 2: I}
(e) {Oil 111/0" 1m, 11 2: I} u {0IlIII/2"'lm, 11 2: I}.
4.3 Test whether 001100, 001010, 01010 are in the language generated by
the grammar given in Exercise 4.I(b).
4.4 Let G = ({A, B, S}, {O, I}, P, S), where P consists of S ~ OAB,
A o ~ SOB, Al ~ SBI. B ~ SA, B ~ 01. Show that L(G) = 0.