Chapter 4: Formal Languages );\ 133
2. If a ~ f3 in a grammar G, then
(a) a ~ f3
(c) f3 ~ a
(b) f3 ~ a
(d) none of these
3. If a -0 f3 is a production in a grammar G, then
(a) aa ~ f3f3
(b) aaf3 ~ f3f3a
(c) aa ~ f3a
(d) aaa ~ f3f3f3
4. If a grammar G has three productions 5 -0 aSa I bsb i e, then
(a) abeba and baeab E L(G)
(b) abcba and abeab E L(G)
(c) aeeea and beecb E L(G)
(d) aeeeh and bceea E L(G)
5. The minimum number of productions for a grammar G = ({S}, to, 1,
2, ..., 9}, P, 5) for generating {O, 1. 2, .... 9} is
(a) 9
(b) 10
(c) 1
(d) 2
6. If G j = (N, T. Pi, S) and G: = (N, T, P:, 5) and Pi C P:, then
(a) L(G i ) C L(G:)
(b) L(G:) C L(G))
(c) L(G!) = L(GJ
(d) none of these.
7. The regular grammar generating {a" : n :::: I} is
(a) ({S}, {a}, {S -0 as}, S)
(b) ({S}, {a}, {S -0 55, 5 -0 aD
(c) ({S}, {a}, {S -0 as}, S)
(d) ({S}, {a}, {S -0 as,S -0 a,S)
8. L = {theory, of. computer, science} can be generated by
(a) a regular grammar
(b) a context-free grammar but not a regular grammar
(c) a context-sensitive grammar but not a context-free grammar
(d) only by a type °grammar.
9. {a" In:::: I} is
(a) regular
(b) context-free but not regular
(c) context-sensitive but not context-free
(d) none of these.
10. {d' b" III : : : : I} is
(a) regular
(b) context-free but not regular
(c) context-sensitive but not context-free
(d) none of these.
11. {d'b"c" In : : : : I} is
(a) regular
(b) context-free but not regular
(c) context-sensitive but not context-free
(d) none of these.