8. The functions which are computable by a Turing Machine are known as
(a) Partial Recursive Functions (b) Enumerable Functions
(c) Partial Functions
(d) Finite-Automata
10. In a digraph, if all the vertices have the same outer degree, then it is
known as
(a) Connected Graph
(b) Euler Graph
(c) Hamiitonion Graph
(d) Regular Graph
GROUP II
11. Which Automation is used for accepting Regular Expressions? Write
the definition for it.
12. Define “prefix” and “suffix” of a string.
13. When an NFA becomes a DFA?
14. What is CNF? and What is GNF? Define.
15. Write the definition of Context-Free Grammar.
16. Define “Unit Production” and “Null Production”.
17. Write the definition of “Turing machine”.
18. What is meant by Recursively Enumerable language?
19. What is meant by Partial Recursive Function?
20. When a “digraph” becomes a “regular graph”?
SEMESTER EXAMINATIONS
(NOV./DEC. 1999)
M.Sc. — COMPUTER TECHNOLOGY — I SEMESTER
THEORY OF COMPUTING
Time : 3 hours
Max. Marks: 60
Instruc tions
1. Answer ALL questions from Part A and FIVE questions from Part B.
2. All questions must be answered in same answer book.
PART A
1. Define regular expression.
University Question Papers
321