GATE Overflow Newsletter

for the period between Sep 26, 2017 and Oct 3, 2017

+5

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

+3

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

+5

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**

+4

In the given question , L_{U }is 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 L_{U} has this property..In other words , L_{U } represents a recursive language (or a recursive set)..

Now given reduction : L ā¤ L_{U}

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 , L_{U} is a recursive language , so due to the reduction : L ā¤ L_{U }, L is recursive as well..

**Hence option C) should be correct..**

+4

**L1 = {0 ^{n+m}1^{k+l} | m = l, m, n, k, l >=1}**

We can write it as

L1 = {0

L1 = {0

**L2 = {0 ^{n}(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.

+4

$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.

+4

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

Hence a^{10} = e where e is the identity element but we dont know about a^{8}..Hence we have to write it in terms of a^{10} as that is a known result.

Let we have y = a^{40} which can be written as : a^{40} = (a^{10})^{4} = e^{4} = e ...(1)

Also , a^{40} = (a^{8})^{5} = e [ Follows from (1) ]

Hence it means that a^{8} 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 a ^{8} = 5 **

Is it neccessary to solve all questions from excercise of reference books for preparation of gate?topAnd after that some test series should be enrolled in for time management and temperament improvement purpose..

Lexical analyser, TokenstopThis 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.

https://gcc.gnu.org/onlinedocs/cpp/Tokenization.html

Regular expressionstopGATE2005-65topIf 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.

DAG COMPILERtop