THEORY OF COMPUTING
GROUP I
(ANSWER ALL QUESTIONS)
1. Let a and b be two regular expressions then (
)
* *
a
b
∗
∪
is equivalent to
(a) a b
∪
(b) (
)
*
a b
∪
(c) (
)
*
b a
∪
(d) (
)
*
* *
b
a
∪
2. Every context free Grammar can be transferred into an equivalent
(a) Greibach Normal Form (GNF)
(b) Chomsky Normal Form (CNF)
(c) Either (A) or (B)
(d) None of the above
3. Finite state machine — recognizes palindromes
(a) can
(b) may
(c) Can’t
(d) may not
4. Pushdown machine represents
(a) Type 3 regular grammar
(b) Type 2 context free grammar
(c) Type 1 context sensitive grammar
(d) Type 0 phrase structural grammar
5. The Turing machine is computable if final state contains
(a) transition function
(b) no tansition function
(c) halt state
(d) both B and C
6. Match the following
1. BNF
(a) S
aAa A SbA
→
→
,
2. CNF
(b) S
aAA A bBB
→
→
,
3. GNF
(c) S
AA A a
→
→
,
(A) 1-a, 2-b, 3-c,
(B) 1-b, 2-c, 3-a
(C) 1-a, 2-c, 3-b
(D) 1-c, 2-b, 3-a.
7. Which is the data structure used to implement the PDA?
(a) Linked list
(b) queue
(c) stack
(d) Array
8. A connected graph as a strongly regular colouring if and only if it is a
(a) digraph
(b) cayley graph
(c) regular graph
(d) cellular Automata.
9. Which is the following is a model of massive parallelism.
(a) Finite Automata
(b) Linear Bounded Automata
(c) Turing machine
(d) Cellular Automata
324
Theory of Automata, Formal Languages and Computation