Uni ver sity Ques tion Papers
THEORY OF COMPUTING
GROUP I
(ANSWER ALL QUESTIONS)
1. The positive closure operator denotes
(a) Proper suffix
(b) Proper prefix
(c) One or more occurrance
(d) the length of string is zero
2. Type 3 Grammars are known as
(a) Regular Grammar
(b) Context Sensitive Grammar
(c) Context Free Grammar
(d) Unrestricted Grammar
3. If a grammar produces more than one parse free for a sentence, the
grammar is known as
(a) Left Linear Grammar
(b) Ambiguous Grammar
(c) Context Free Grammar
(d) Regular Grammar
(4) Which is the data structure used to implement the Push Down
Automata?
(a) Linked List
(b) Queue
(c) Stack
(d) Array
5. The graphical representation of derivation is known as
(a) Derivation Tree
(b) Derivation structure
(c) Linear Graph
(d) Cellular Automata
6. An unrestricted language can be accepted by
(a) Finite Automata
(b) Turing Machine
(c) Push Down Automata
(d) Cellular Automata
7. The grammar with the productions
S
aA
→
and A → ε ε
( -epsilon) belongs to
(a) Regular Grammar only
(b) Context-Free Grammar only
(c) Regular Grammar and context-free grammar
(d) Context sensitive grammar.