GATE Overflow Newsletter
for the period between Sep 26, 2017 and Oct 3, 2017

Top New Questions

Ttotal number of BST's possible with 6 nodes numbered 1,2,3,4,5 and 6 having a height of 4 are ??


please give proper reasoning.

In case of right shift bitwise operator in ā€˜Cā€™ language, after shifting n bits, the left most n bits:
(A) are always filled with zeroes
(B) are always filled with ones
(C) are filled with zeroes or ones and is machine dependent
(D) none of the above


Top New Answers

In response to the question DAG COMPILER top

The idea of making DAG of a given expression is to construct corresponding syntax tree first and then we find the common occurence in the tree and join these common occurence to their common parent ; indicating that the same units are not taken repeatedly..This is shown as follow :



Hence number of internal nodes  =  3

Number of leaf node   =   1

Number of edges in DAG  =   6

In response to the question UTM REDUCTION top

In the given question , Lis a set of strings which are accepted by the Universal Turing Machine..In order words , these are the strings in which the given Turing machine halts and each of the string of LU has this property..In other words , L represents a recursive language (or a recursive set)..

Now given reduction :   L  ā‰¤  LU

Now we know that for easy problems (or) languages [ REC (or) decidable , RE , P , NP ] , reduction works right to left i.e. if the class of the right part of the reduction is known , then we can deduce the left part also..But other way round , we cannot conclude anything..

As here , LU is a recursive language , so due to the reduction : L  ā‰¤  LU  , L is recursive as well..

Hence option C) should be correct..


L1 = {0n+m1k+l | m = l, m, n, k, l >=1}
We can write it as
L1 = {0n0m1k1l | m = l, m, n, k, l >=1},Since m and l does not depend upon n and k, we can fix its value as 1, and use n and k to take remaining 0's and 1's, so our language become..
L1 = {0n01k1 |  n, k >=1}Now we just need to check for any number of 0 followed by a 0, then any number of 1 followed by a 1, which is regular.

L2 = {0n(11)m | m,n >=0}
Any number of zeros followed by even number of 1's, its regular.

According to me option D is correct, both L1 and L2 are regular.

In response to the question GATE Aptitude top

$8\\ 8\times1-2=6\\ 6 \times2-3=9\\ 9 \times 3 - 4=23\\ 23 \times 4-5=87\\ 87 \times 5-6=429$


Hence, Option(D)429 is the correct choice.


Here we are given that the order of the group is 10 and a is the generator..

Hence  a10  =  e  where e is the identity element but we dont know about a8..Hence we have to write it in terms of a10 as that is a known result.

Let we have   y  =  a40   which can be written as :    a40  =   (a10)4   =  e4   =   e    ...(1) 

                                                            Also ,        a40   =  (a8)5     =  e     [ Follows from (1) ]

Hence it means that  a8 is repeated 5 times in order to get the identity element e which is least number of times to do so.

Also from the corollary of the Lagranges' Theorem , 

Order of an element  divides the order of the order of the group (The actual theorem is order of a subgroup divides the order of the group)

Here 5 divides the order of group i,e, 10..

Hence order of  a8   =   5 

Top New Comments

Textbook reading should be done for understanding purpose..Having done that u should do the previous year questions.If u have time after that , then u can solve exercise questions of textbook..

And after that some test series should be enrolled in for time management and temperament improvement purpose..


This will be consider as single token, because compiler apply greedy approach for performing tokenization, it will try to include more character in token if possible.

$(a+b)^{*}\equiv (a^{*}+b^{*})^{*}\equiv (a^{*}+b)^{*}\equiv (a+b^{*})^{*}\equiv (a^{*}b^{*})^{*}\equiv(b^{*}a^{*})^{*}$

In response to an answer on the question GATE2005-65 top
@Just_bhavana , Register access time is much less than memory access time hence it is not counted..

If it were asked  "no of memory cycles needed for decode and execute phase"..Then in decode phase , we access the second and third word of instruction..So total cycles needed in decode and execute phase = 4 + 2 = 6.

In response to the question DAG COMPILER top
3 Internal node and 1 leaf node