224 ~ Theory of Computer Science
3. State whether the following statements are true or false.
(a) A regular language is context-free.
(b) There exist context-free languages that are not regular.
(c) The class of context-free languages is closed under union.
(d) The class of context-free languages is closed under intersection.
(e) The class of context-free languages is closed under
complementation.
(f) Every finite subset of {a, b}* is a context-free language.
(g) {a
l b"c
17
ln ~ I} is a context-free language.
(h) Any derivation tree for a regular grammar is a binary tree.
EXERCISES
6.1 Find a derivation tree of a , b + a * b given that a * b + a * b is in
L(G), where G is given by 5 ~ 5 + SiS " S, S ~ alb.
6.2 A context-free grammar G has the following productions:
S ~ OSOllSlIA,
A ~ 2B3.
B ~ 2B313
Describe the language generated by the parameters.
6.3 A derivation tree of a sentential form of a grammar G is gIven m
Fig. 6.15.
X 1
X 3
X 3
Fig. 6.15 Derivation tree for Exercise 6.3.
(a) What symbols are necessarily in V:v?
(b) What symbols are likely to be in 2:?
(c) Determine if the following strings are sentential forms: (i) X 4 X 20
(ii) X2X2X3X2X3X3, and (iii) X 2 X 4 X 4 X 2 .
6.4 Find (i) a leftmost derivation, (ii) a rightmost derivation, and (iii) a
derivation which is neither leftmost nor rightmost of abababa,
given that abababa is in L(G), where G is the grammar given in
Example 6.4.