GATE CS 2021 : National champion Quiz-4 (App update required to attempt this test)

Consider the following production rules:

The output of 2 * 4 # 7 # 1 * 5 # 2 * 8 # 3 expression is ________.

Consider the following SDT:

What is the missing translation (1) and (2), if the string “2 × 3 + 5 × 3 + 1 × 3” produces 160 instead of 24?

Given the following attribute grammar:

E → TE’             E’.y = E.x

                        E.x = E’.y

E₁’ → + TE₂’      E₂’.y = E₁’.y + T.x

                        E₁’.x = E₂’.x

Which of the following is true?

Which of the following is correct about self-relocating program?

Consider the following statements:

I. Pointer variables are allocated on the stack.

II. Optimal use of registers in the code generation is NP complete and possibly intractable.

III. LEX compiler transforms the input patterns into a transition diagram and generates code in a file.

IV. YACC is a representation of an LALR parser written in C.

The number of correct statements is:

Consider the following statements:

A) Static allocation bindings do not changes at run time

B) Heap allocation allocates and de-allocates storage at run time.

C) Recursion in programming languages cannot be implemented with dynamic storage allocation.

How many of the above statements are false?

Let M be a finite automaton. Let M′ denote the machine obtained by interchanging the initial and final states in the machine M.

I. L(M) L(M’) =

II. L(M)  L(M’) =

What is the validity of the above statements with respect to DFAs and NFAs?

A Language is said to be regular iff- (Multi Select Question)

The number of states in the minimal DFA of the set of strings over {0, 1} in which first 3 symbols are same, is ________.

Which of the following is a valid description of the input alphabet set  ? (Multi Select Question)

Consider the following Problems:

P₁: {<M, x, k> | M is a TM and M does not halt on x with in k steps}

P₂: {<M> | M is a TM and. M accepts atleast two strings of different length}

P₃ : {<M> | M is a TM and there exist an input whose length is less than 100, on which M halts}

The problem which is/are RE but not REC is _______.(Multiple Select Question)

Consider the following language:

L₁ = {<M> |M is TM, M₀ is TM that halts on all inputs, and M ϵ L(M₀)}

L₂ = {<M>} | M is TM, M₀is TM that halts on all inputs, and M₀ϵ L(M)}

Which of the following is correct above languages?