ISRO Scientist or Engineer Computer Science 2016

Algorithm design technique used in quick sort algorithm is

An FSM (Finite State Machine) can be considered to be a Turning Machineof finite tape length

Let $$L = \left\{\omega \epsilon (0+1)*|  \omega \right\}$$ has even number of 1s, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?

Consider the following recurrence
$$T(n)=2T(\sqrt{n})+1$$
$$T(1) = 1$$
Which of the following is true?

Consider the following statements about the context-free grammar:
$$G = \left\{S \rightarrow SS,S \rightarrow ab, S \rightarrow ba, S\rightarrow \wedge \right\}$$
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III.G can be accepted by a deterministic PDA
Which combinations below expresses all the true statements about G?

If L and $$\overline{L}$$ are recursively enumerable , then L is

$$S \rightarrow a Sa|bSb|a|b$$
The language generated by the above grammar over the alphabets { a, b } is the set of

What is the highest type number that can be assigned to this following grammar : $$S \rightarrow Aa, A \rightarrow Ba, B \rightarrow abc$$

Access time of the symbol table will be logarithmic, if it is implemented by

Recursive descent parsing is an example of