U.G.C. NET Exam. 24 June, 2019 Paper–II (COMPUTER SCIENCE & APPLICATIONS)

Total Questions: 100

71. Which data structure is used by the compiler for managing variables and their attributes?

Correct Answer: (c) Symbol table
Solution:

Symbol table
It can be implemented by using an array, hash table, tree and even some time with the help of the linked list.

72. On translating the expression given below into quadruple representation, how many operations are required?

(i * j) + (e + f) * (a * b + c )

Correct Answer: (b) 6
Solution:

73. How many states are there in a minimum state automata equivalent to regular expression given below?

Regular expression is a * b(a + b)

Correct Answer: (c) 3
Solution:

Regular expression :
a * b (a + b)
Language that is accepted by this expression is of type : {ba, bb, bab, aba, abb, abab, aabab,.......} Smallest string length is 2, that is, we need at least 3 states for this.
NFA for this regular expression is :

So number of states required in this NFA are 3.

74. Match List-I with List-II

Correct Answer: (b) (A)-(ii), (B)-(iii), (C)-(i)
Solution:

75. How can the decision algorithm be constructed for deciding whether context-free language L is finite?

Correct Answer: (c) (C) only
Solution:

We can check that whether a context free language L is finite or not by contracting non redundant context free grammar in which there are no null productions no unit productions and no useless productions. Steps that are used in deciding whether a context free language is finite or not?
1) Construct the context free grammar corresponding to that language.
2) Reduce the grammar by removing null, unit and useless productions.
3) Contract the directed graph of that grammar
4) If that graph contains a cycle, then that language is infinite.
If graph does not contain cycle, it means language is finite.

76. Replacing the expression 4 * 2.14 by 8.56 is known as

Correct Answer: (a) constant folding
Solution:

Constant folding is compiler optimizations technique used by many modern compilers. Constant folding is the process of recognizing and evaluation constant expressions at compile time rather than computing them at runtime
Example :
int var = 4 * 2.14;
Replace with
int var = 8.56
Since multiplication is costly operation, it has been replaced constant which is more optimized version of previous code.

77. Shift-reduce parser consists of

(a) input buffer
(b) stack
(c) parse table
Choose the correct option from those give below :

Correct Answer: (d) (a), (b) and (c)
Solution:

Sift reduce parser is based on the idea of predictive parsing with Look ahead. It is a bottom up parser.
Shift reduce parser generates a parse tree for an input string from bottom to top. At the end, reaches to the start symbol of the grammar. For a shift reduce parse, two data structure are required : one is stack and another in input buffer. Stack is used to keep the grammar symbols and input buffer hold the string to be parsed. Initially both the stack and input buffer contain the $ symbol.

78. Consider the following grammar :

Correct Answer: (d) (C) and (D) only
Solution:

S → XY

79. Which of the following problems is/are decidable problem(s) (recursively enumerable) on turning machine M?


Correct Answer: (c) (A), (B) and (C)
Solution:

80. For a statement

Correct Answer: (c) It ω ∉ L, the M halts without reaching to acceptable state
Solution:

A language is recursive if there exists a Turing machine. For strings that are in the language, Turing machine accepts the language and always halts and for strings not in the language, string will halt in the non final state.
Explanation :-
A language L ⊆ ∑ * is recursive if there exists some Turing machine M suppose w is the string. So if w belongs to language, then Turing machine M will halt by reaching at final state and if does not belong to L, then M halts without reaching to final state (acceptable state).