U.G.C. NET Exam. 4 December, 2019 Paper II (COMPUTER SCIENCE & APPLICATIONS)

Total Questions: 100

41. When using Dijkstra's algorithm to find shortest path in a graph, which of the following statement is not true?

Correct Answer: (c) Shortest path always passes through least number of vertices
Solution:Dijkstra's algorithm is used to find single source shortest path i.e. path between any two vertices in a graph. All edges must have non-negative weights and graph must be connected.
So, we get the shortest distance from a to g. (a → b → c → d → f → g).

42. The time complexity to multiply two polynomials of degree n using Fast Fourier transform method is:

Correct Answer: (a)
Solution:

Fast Fourier transform is a discrete Fourier transform algorithm which reduces the number of computation needed for N points from 2N² to 2N log N.
A discrete Fourier transform can be computed using fast Fourier transform by means of Daniel-Sonlanczos lemma, if the number of point N is a Power of two. If number of points N is not a power of two, a transform can be performed n sets of points corresponding to prime factor of N.
Fast Fourier transform allows computing in 0(n log n) time. Basic idea is to apply divide and conquer. We divide the co-efficient vector of polynomial into two vectors, recursively compute the Discrete Fourier transform for each of them and combine the results Recursive relation will become;

43. Consider the following grammars:

Correct Answer: (c)
Solution:

44. Answer the following question

Correct Answer: (d) S→aaaA, A→aAb|λ
Solution:

for n = 3, string generated = aaa for n = 4, string generated = aaaab for n = 5 string generated = aaaaabb only option 4 can generate the above grammar at following value of n

45. Consider the following grammar :

S → 0A|0BB
A → 00A|λ
B → 1B|11C
C → B
Which language does this grammar generate ?

Correct Answer: (c) L((00)*0)
Solution:

Given grammar is generating string of type: {0,000,00000,0000000...........}
(1) L((00) * 0 + (11) * 1 )
This language generating string with combination of 0'S and 1 and But given Grammar is not generating any string composed of 1's.

46. Answer the following question

Correct Answer: (b) (zxyy+(xzy)*)(zxyyzxyy)*
Solution:

Homomorphism is a function from string to string that is based on the concatenation for any x and y ∈∑* h(x,y) = h(x) h(y)
L is the regular language with the regular expression r =
(w + x*) (ww)*
Then h(L) = (h(w) + h(x)*) (h(w)h(w))*
Given : h(x) = xzy
h(w) = zxyy
h(L) = (zxyy+(xzy)*) (zxyy zxyy)*

47. Answer the following question

Correct Answer: (d)
Solution:

48. Answer the following question

Correct Answer: (a)
Solution:

49. Let G = (V,T,S,P)be any context - free grammar without any λ-productions or unit production Let K be the maximum number of symbols on the right of any production in P. The maximum number of production rules for any equivalent grammar in Chomsky normal from is given by:

Correct Answer: (b) (K–1)|P| + |T|
Solution:

Context free Grammar :- A grammar G = (V,T,S,P) is said to be context- free if all productions in P have the from A →X Where A∈V and X∈(V U T)* If context the grammar G = (V,T,S,P) is without λproductions or unit productions. K = maximum number of symbols on right-side of production.
The maximum number of production rules for equivalent grammar in CNF: (K–1)|P|+|T| A context free grammar is in CNF (Chomsky normal form) if it satisfies these conditions: 1. Should not contains null or unit productions. 2. A non- terminal symbol generating two non-terminals for examples S →AB 3. A non-terminal generating a terminal example: S →a

50. Consider the following language families:

Correct Answer: (c)
Solution:

Context free languages:- A language is said to be context free if and only if there exists a context free grammar for it. A grammar G = (V,T,S,P) is said to be context free is all production is in the form of A→X where A∈V and X∈(V∪T)*. There are accepted by push down .........
Context sensitive languages:- If there exists a context sensitive grammar for a language then it is known context sensitive language context sensitive grammar is one in which all production are of the from x→y where x,y ∈(V∪T)* and x< = y these are accepted by linear bounded automata.
Recursive language:- A language is recursive if there exists a Turing machine accepts it and halts on every input string .
Recursive enumerable languages : A language is recursive enumerable if there exists some Turing machine which accepts it.