Andhra University 2006 B.E Information Technology COMPUTER SCIENCE

Which of the subsequent statements is true?
L is recursive
L is recursively enumerable but not recursive
L is not recursively enumerable
Whether L is recursive or not will be known after we obtain out if P = NP



14. The regular expression 0* (10*)* denotes the identical set as
(1*0)*1*
0 + (0 + 10)*
(0 + 1)* 10(0 + 1)*
none of the above

15. If the strings of a language L .can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the subsequent statements is true?

(a) L is necessarily finite

(b) L is regular but not necessarily finite

(c) L is situation free but not necessarily regular

(d) L is recursive but not necessarily situation free



16. Which of the subsequent suffices to convert an arbitrary CFG to an LL(1) grammar ?

(a) Removing left recursion alone

(b) Factoring the grammar alone

(c) Removing left recursion and factoring the grammar

(d) None of the above



17. presume that the SLR parser for a grammar G has n one states and the LALR parser for G has n two states. The relationship ranging from n l and n two is

(a) n one is necessarily less than n2

(b) n one is necessarily equal to n2

(c) n one is necessarily greater than n2

(d) none of the above



18. In a bottom-up valuation of a syntax directed definition, inherited attributes can

(a) always be evaluated

(b) be evaluated only if the definition is L-attributed

(c) be evaluated only if the definition has synthesized attributes

(d) never be evaluated



19. Suppose the numbers 7, 5, 1, 8, 3, 6, 0, 9, 4, two are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resulting tree?
7 five one 0 three two four six eight nine
0 two four three one six five nine eight seven
0 one two three four five six seven eight nine
9 eight six four two three 0 one five seven



20. Consider the subsequent 3 claims
(n + k) m = Q (n m), where k and m are constants

Earning:   Approval pending.