(i) 10 (ii) 0*1* (iii) {0, 1}*{10} (iv) (101)*
(A) (i) only
(B) (i) & (ii) only
(C) (i) & (iii) only
(D) (ii) & (iii) only
3. The context free grammar defined by ab* is
(a) S
Sb a
→ /
(b) S
XY X
ax Y
by
→
→
→
,
,
(c) C
SS baa abb S
→
→
/
/
,
ε (d) S
aS S
bS
→
→
,
.
4. Find the useless symbol in the given CFG
S
AB CA B
BC AB A a C
aB b
→
→
→
→
/ ,
/
,
;
/
(a) A
(b) B
(c) C
(d) all of the above.
5. The grammar that does not have an equivalent deterministic automata
for a non-deterministic one is
(a) Finite state automata
(b) Turing machine
(c) Pushdown automata
(d) None of the above
6. A CFG is ambiguous if
(a) The grammar contains useless Non-Terminals.
(b) It produces more than one parse tree for some sentence.
(c) Some productions has two Non-Terminals side by side.
(d) The grammar contains only terminals on the right side.
7. Which of the following is a model of massive parallelism
(a) Cellular automata
(b) Turing machine
(c) Linear bounded automata (d) Finite automata
8. When a connected graph has a strongly regular coloring
(a) If the graph is a digraph
(b) If the graph is a Cayley graph
(c) If the graph is a Euler graph.
(d) If the graph is a Hamiltonian graph.
9. Match the following
(a) BNF
(i) S
AA A BB B
a
→
→
→
,
,
(b) CNF
(ii) S
aAA A bBB B
b
→
→
→
,
,
(c) GNF
(iii) S
aAa A SA A b
→
→
→
,
,
(a) a - i, b - iii, c - ii
(b) a - ii, b - iii, c - i
(c) a - i, b - ii, c - iii
(d) a - iii, b - i, c - ii.
10. If ‘a’ and ‘x’ as configuration with finite support and ‘x’ be an arbitrary
configuration then the convolution a*x is given by.
326
Theory of Automata, Formal Languages and Computation