![Mcqmate logo](https://mcqmate.com/public/images/logos/logo-black.png)
![Mcqmate logo](https://mcqmate.com/public/images/logos/logo-white.png)
McqMate
1. |
Let L={w \in (0 + 1)*|w 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? |
A. | (0*10*1)* |
B. | 0*(10*10*)* |
C. | 0*(10*1*)*0* |
D. | 0*1(10*1)*10* |
Answer» B. 0*(10*10*)* |
2. |
Consider the languages
|
A. | Only L2 is context free |
B. | Only L2 and L3 are context free |
C. | Only L1 and L2 are context free |
D. | All are context free |
Answer» D. All are context free |
3. |
Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L? |
A. | n-1 |
B. | n |
C. | n+1 |
D. | 2n-1 |
Answer» C. n+1 |
4. |
Let L = L1 \cap L2, where L1 and L2 are languages as defined below: L1 = {a^{m}b^{m}ca^{n}b^{n} | m, n >= 0 } L2 = {a^{i}b^{j}c^{k} | i, j, k >= 0 } Then L is |
A. | Not recursive |
B. | Regular |
C. | Context free but not regular |
D. | Recursively enumerable but not context free. |
Answer» C. Context free but not regular |
5. |
Consider the language L1,L2,L3 as given below.
|
A. | Push Down Automata (PDA) can be used to recognize L1 and L2 |
B. | L1 is a regular language |
C. | All the three languages are context free |
D. | Turing machine can be used to recognize all the three languages |
Answer» C. All the three languages are context free |
6. |
Definition of a language L with alphabet {a} is given as following. L= { a^{nk} | k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L? |
A. | k+1 |
B. | n+1 |
C. | 2^(n+1) |
D. | 2^(k+1) |
Answer» B. n+1 |
7. |
Which of the following problems are decidable?
|
A. | 1, 2, 3, 4 |
B. | 1, 2 |
C. | 2, 3, 4 |
D. | 3, 4 |
Answer» D. 3, 4 |
8. |
Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For examples, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are |
A. | A |
B. | B |
C. | C |
D. | D |
Answer» D. D |
9. |
Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression |
A. | b*ab*ab*ab |
B. | (a+b)* |
C. | b*a(a+b)* |
D. | b*ab*ab |
Answer» C. b*a(a+b)* |
10. |
The minimum state automaton equivalent to the above FSA has the following number of states |
A. | 1 |
B. | 2 |
C. | 3 |
D. | 4 |
Answer» B. 2 |
11. |
Which of the following languages is regular? |
A. | {WW^R | W € {0,1}+ } |
B. | {WW^R X | X W € {0,1}+ } |
C. | {WW^R | X W € {0,1}+ } |
D. | {XWW^R | X W € {0,1}+ } |
Answer» C. {WW^R | X W € {0,1}+ } |
12. |
The language L = { 0^i 2 1 ^i i>-0 } over the alphabet (0,1,2) is |
A. | not recurcise |
B. | is recursive and deterministic CFL |
C. | is a regular language |
D. | is not a deterministic CFL but a CFL |
Answer» B. is recursive and deterministic CFL |
13. |
A minimum state deterministic finite automation accepting the language L = {W |W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has |
A. | 15 States |
B. | 11 states |
C. | 10 states |
D. | 9 states |
Answer» A. 15 States |
14. |
If s is a string over (0 + 1)* then let n0 (s) denote the number of 0’s in s and n1 (s)the number of l’s in s. Which one of the following languages is not regular? |
A. | L = {s € (0 + 1)*n0 (s) is a 3-digit prime |
B. | L = {s € (0 + 1)* | for every prefix s’ of s, l 0 (s’) — n1 (s’) | <= 2 } |
C. | L={s € (0+1)* | n0(s) - n1(s) | <= 4} |
D. | L = {s € (0 + 1) | n0 (s) mod 7 = n1 (s) mod 5 = 0 } |
Answer» C. L={s € (0+1)* | n0(s) - n1(s) | <= 4} |
15. |
For S € (0+1)* let d(s)denote the decimal value of s(e.g.d(101)= 5).Let L = {s € (0 + 1) | d (s) mod 5 = 2 and d (s) mod 7 != 4)}Which one of the following statements is true? |
A. | L is recursively enumerable, but not recursive |
B. | L is recursive, but not context-free |
C. | L is context-free, but not regular |
D. | L is regular |
Answer» D. L is regular |
16. |
Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true? |
A. | Both DHAM3 and SHAM3 are NP-hard |
B. | SHAM3 is NP-hard, but DHAM3 is not |
C. | DHAM3 is NP-hard, but SHAM3 is not |
D. | Neither DHAM3 nor SHAM3 is NP-hard |
Answer» A. Both DHAM3 and SHAM3 are NP-hard |
17. |
Consider the following statements about the context free grammarG = {S - >SS, S - >ab, S - >ba, S - ε}I. G is ambiguousII. G produces all strings with equal number of a’s and b’sIII. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G? |
A. | 1 only |
B. | 1 and 3 |
C. | 2 and 3 |
D. | 1,2 and 3 |
Answer» D. 1,2 and 3 |
18. |
Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false? |
A. | L1 n L2 is a deterministic CFL |
B. | L3 n L1 is recursive |
C. | L1 U L2 is context free |
D. | L1 n L2 n L3 is recursively enumerable |
Answer» B. L3 n L1 is recursive |
19. |
Consider the regular language L =(111+11111)*. The minimum number of states |
A. | 3 |
B. | 5 |
C. | 8 |
D. | 9 |
Answer» D. 9 |
20. |
Consider the languages: GATE[2005]L1 = {wwR w €{0, 1} *1L2 ={w#ww € {O,1}*},where # is a special symbolL3 ={www € {0,1}*}Which one of the following is TRUE? |
A. | L1 is a deterministic CFL |
B. | L2 is a deterministic CFL |
C. | L3 is a CFL, but not a deterministic CFL |
D. | L3 is a deterministic CFL |
Answer» B. L2 is a deterministic CFL |
21. |
Consider the languages: L1 ={a^n b^n c^m | n,m >01 and L2 ={a^n b^m c^m |n,m> o) Which one of the following statements is FALSE? |
A. | L1 n L2 is a context-free language |
B. | L1 u L2 is a context-free language |
C. | L1 and L2 are context-free languages |
D. | L1 n L2 is a context sensitive language |
Answer» A. L1 n L2 is a context-free language |
22. |
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE? |
A. | L1' is recursive and L2' is recursively enumerable |
B. | L1' is recursive and L2' is not recursively enumerable |
C. | L1' and L2' are recursively enumerable |
D. | L1' is recursively enumerable and L2' is recursive |
Answer» B. L1' is recursive and L2' is not recursively enumerable |
23. |
Consider the following two problems on undirected graphs:
|
A. | α is in P and β is NP-complete |
B. | α is NP complete and β is in P |
C. | Both α and β are NP-complete |
D. | Both α and β are in P |
Answer» B. α is NP complete and β is in P |
24. |
Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true? |
A. | L2 – L1 is recursively enumerable. |
B. | L1 – L3 is recursively enumberable |
C. | L2 intersection L1 is recursively enumberable |
D. | L2 union L1 is recursively enumberable |
Answer» B. L1 – L3 is recursively enumberable |
25. |
S –> aSa| bSb| a| b ; The language generated by the above grammar over the alphabet {a,b} is the set of |
A. | All palindromes. |
B. | All odd length palindromes. |
C. | Strings that begin and end with the same symbol |
D. | All even length palindromes. |
Answer» B. All odd length palindromes. |
26. |
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*? |
A. | The set of all strings containing the substring 00. |
B. | The set of all strings containing at most two 0’s. |
C. | The set of all strings containing at least two 0’s. |
D. | The set of all strings that begin and end with either 0 or 1. |
Answer» C. The set of all strings containing at least two 0’s. |
27. |
Which one of the following is FALSE? |
A. | There is unique minimal DFA for every regular language |
B. | Every NFA can be converted to an equivalent PDA. |
C. | Complement of every context-free language is recursive. |
D. | Every nondeterministic PDA can be converted to an equivalent deterministic PDA. |
Answer» D. Every nondeterministic PDA can be converted to an equivalent deterministic PDA. |
28. |
Match all items in Group 1 with correct options from those given in Group 2.
|
A. | P-4. Q-1, R-2, S-3 |
B. | P-3, Q-1, R-4, S-2 |
C. | P-3, Q-4, R-1, S-2 |
D. | P-2, Q-1, R-4, S-3 |
Answer» B. P-3, Q-1, R-4, S-2 |
29. |
Which of the following pairs have DIFFERENT expressive power? |
A. | Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA) |
B. | Deterministic push down automata (DPDA) and Non-deterministic pushdown automata |
C. | Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine |
D. | Single-tape Turing machine and multi-tape Turing machine |
Answer» B. Deterministic push down automata (DPDA) and Non-deterministic pushdown automata |
30. |
Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true? |
A. | ScT (S is a subset of T) |
B. | TcS (T is a subset of S) |
C. | S=T |
D. | SnT=Ø |
Answer» C. S=T |
31. |
Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true? |
A. | L = O |
B. | L is regular but not O |
C. | L is context free but not regular |
D. | L is not context free |
Answer» B. L is regular but not O |
32. |
Consider the following two statements:
|
A. | Only S1 is correct |
B. | Only S2 is correct |
C. | Both S1 and S2 are correct |
D. | None of S1 and S2 is correct |
Answer» C. Both S1 and S2 are correct |
33. |
Which of the following statements in true? |
A. | If a language is context free it can always be accepted by a deterministic push-down automaton |
B. | The union of two context free languages is context free |
C. | The intersection of two context free languages is context free |
D. | The complement of a context free language is context free |
Answer» B. The union of two context free languages is context free |
34. |
Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least. |
A. | N^2 |
B. | 2^N |
C. | 2N |
D. | N! |
Answer» B. 2^N |
35. |
Which of the following is true for the language {a^p} p is prine ? |
A. | It is not accepted by a turing machine |
B. | It is regular but not context free |
C. | It is context free but not regular |
D. | It is neither regular nor context free but accepted by a turing machine |
Answer» D. It is neither regular nor context free but accepted by a turing machine |
36. |
Which of the following are decidable ?
|
A. | 1 and 2 |
B. | 1 and 4 |
C. | 2 and 3 |
D. | 2 and 4 |
Answer» B. 1 and 4 |
37. |
If L and L' are recursively enumerable, then L is |
A. | regular |
B. | context free |
C. | context sensitive |
D. | recursive |
Answer» D. recursive |
38. |
Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules
|
A. | aaaabb |
B. | aabbbb |
C. | aabbab |
D. | abbbba |
Answer» C. aabbab |
39. |
Consider the following context free languages:
|
A. | L1, L2 and L3 can be recognized by Deterministic Push down automata |
B. | L1, L2 can be recognized by Deterministic Push down automata |
C. | L1, L3 can be recognized by Deterministic Push down automata |
D. | None of the above |
Answer» C. L1, L3 can be recognized by Deterministic Push down automata |
40. |
Which of the following are decidable?
|
A. | I and II |
B. | I and IV |
C. | II and III |
D. | II and IV |
Answer» B. I and IV |
41. |
Let <M> be the encoding of a Turing machine as a string over ∑= {0, 1}. Let L = { <M> |M is a Turing machine that accepts a string of length 2014 }. Then, L is |
A. | decidable and recursively enumerable |
B. | undecidable but recursively enumerable |
C. | undecidable and not recursively enumerable |
D. | decidable but not recursively enumerable |
Answer» B. undecidable but recursively enumerable |
42. |
Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE? |
A. | P3 is decidable if P1 is reducible to P3 |
B. | P3 is undecidable if P3 is reducible to P2 |
C. | P3 is undecidable if P2 is reducible to P3 |
D. | P3 is decidable if P3 is reducible to P2's complement |
Answer» C. P3 is undecidable if P2 is reducible to P3 |
43. |
Consider the following decision problems:
|
A. | Both (P1) and (P2) are decidable |
B. | Neither (P1) nor (P2) are decidable |
C. | Only (P1) is decidable |
D. | Only (P2) is decidable |
Answer» A. Both (P1) and (P2) are decidable |
44. |
Which of the following statements is false? |
A. | Every context-sensitive language is recursive. |
B. | The set of all languages that are not recursively enumerable is countable. |
C. | The family of recursively enumerable languages is closed under union. |
D. | The families of recursively enumerable and recursive languages are closed under reversal |
Answer» B. The set of all languages that are not recursively enumerable is countable. |
45. |
In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier? |
A. | (L + D) * |
B. | (L.D) * |
C. | L(L + D) * |
D. | L(L.D) * |
Answer» C. L(L + D) * |
46. |
The number of strings of length 4 that are generated by the regular expression (0+1+|2+3+)*, where | is an alternation character and {+, *} are quantification characters, is: |
A. | 08 |
B. | 09 |
C. | 10 |
D. | 12 |
Answer» C. 10 |
47. |
The regular grammar for the language L = {anbm | n + m is even} is given by |
A. | S → S1 | S2 S1 → a S1| A1 A1 → b A1| λ S2 → aaS2| A2 A2 → b A2| λ |
B. | S → S1 | S2 S1 → a S1| aA1 S2 → aaS2| A2 A1 → b A1| λ A2 → b A2| λ |
C. | S → S1 | S2 S1 → aaa S1| aA1 S2 → aaS2| A2 A1 → b A1| λ A2 → b A2| λ |
D. | S → S1 | S2 S1 → aa S1| A1 S2 → aaS2| A2 A1 → bb A1| λ A2 → bb A2| λ |
Answer» D. S → S1 | S2 S1 → aa S1| A1 S2 → aaS2| A2 A1 → bb A1| λ A2 → bb A2| λ |
48. |
Consider the following identities for regular expressions: (a) (r + s)* = (s + r)* (b) (r*)* = r* (c) (r* s*)* = (r + s)* Which of the above identities are true? |
A. | (a) and (b) only |
B. | (b) and (c) only |
C. | (c) and (a) only |
D. | (a), (b) and (c) |
Answer» D. (a), (b) and (c) |
49. |
For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true? |
A. | L is recursively enumerable, but not recursive |
B. | L is recursive, but not context-free |
C. | L is context-free, but not regular |
D. | L is regular |
Answer» D. L is regular |
50. |
The number of tokens in the following C statement is (GATE 2000) printf("i = %d, &i = %x", i, &i); |
A. | 3 |
B. | 26 |
C. | 10 |
D. | 21 |
Answer» C. 10 |
51. |
In a compiler, keywords of a language are recognized during |
A. | parsing of the program |
B. | the code generation |
C. | the lexical analysis of the program |
D. | dataflow analysis |
Answer» C. the lexical analysis of the program |
52. |
The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense? |
A. | Finite state automata |
B. | Deterministic pushdown automata |
C. | Non-Deterministic pushdown automata |
D. | Turing Machine |
Answer» A. Finite state automata |
53. |
Consider the following statements:
|
A. | Only (I) |
B. | Only (II) and (III) |
C. | All (I), (II), and (III) |
D. | None of these |
Answer» D. None of these |
54. |
Which one of the following statements is FALSE? |
A. | Context-free grammar can be used to specify both lexical and syntax rules. |
B. | Type checking is done before parsing. |
C. | High-level language programs can be translated to different Intermediate Representations. |
D. | Arguments to a function can be passed using the program stack. |
Answer» B. Type checking is done before parsing. |
55. |
A lexical analyzer uses the following patterns to recognize three tokens T1, T2, and T3 over the alphabet {a,b,c}. T1: a?(b∣c)*a T2: b?(a∣c)*b T3: c?(b∣a)*c Note that ‘x?’ means 0 or 1 occurrence of the symbol x. Note also that the analyzer outputs the token that matches the longest possible prefix. If the string bbaacabc is processes by the analyzer, which one of the following is the sequence of tokens it outputs? |
A. | T1T2T3 |
B. | T1T1T3 |
C. | T2T1T3 |
D. | T3T3 |
Answer» D. T3T3 |
56. |
Consider the following statements related to compiler construction :
|
A. | Only I |
B. | Only II |
C. | Both I and II |
D. | Neither I nor II |
Answer» D. Neither I nor II |
57. |
Which of the following statement(s) regarding a linker software is/are true?
|
A. | Only I |
B. | Only II |
C. | Both I and II |
D. | Neither I nor II |
Answer» A. Only I |
58. |
From the given data below : a b b a a b b a a b which one of the following is not a word in the dictionary created by LZ-coding (the initial words are a, b)? |
A. | a b |
B. | b b |
C. | b a |
D. | b a a b |
Answer» D. b a a b |
59. |
The number of tokens in the following C statement is printf("i=%d, &i=%x", i&i); |
A. | 13 |
B. | 6 |
C. | 10 |
D. | 9 |
Answer» D. 9 |
60. |
In compiler optimization, operator strength reduction uses mathematical identities to replace slow math operations with faster operations. Which of the following code replacements is an illustration of operator strength reduction? |
A. | Replace P + P by 2 * P or Replace 3 + 4 by 7. |
B. | Replace P * 32 by P < < 5 |
C. | Replace P * 0 by 0 |
D. | Replace (P < <4) – P by P * 15 |
Answer» B. Replace P * 32 by P < < 5 |
61. |
Debugger is a program that |
A. | allows to examine and modify the contents of registers |
B. | does not allow execution of a segment of program |
C. | allows to set breakpoints, execute a segment of program and display contents of register |
D. | All of the above |
Answer» C. allows to set breakpoints, execute a segment of program and display contents of register |
62. |
Consider the following two sets of LR(1) items of an LR(1) grammar.
|
A. | 1 only |
B. | 2 only |
C. | 1 and 4 only |
D. | 1, 2, 3, and 4 |
Answer» D. 1, 2, 3, and 4 |
63. |
The grammar S → aSa | bS | c is |
A. | LL(1) but not LR(1) |
B. | LR(1)but not LR(1) |
C. | Both LL(1)and LR(1) |
D. | Neither LL(1)nor LR(1) |
Answer» C. Both LL(1)and LR(1) |
64. |
Which of the following statements are TRUE?
|
A. | I and II |
B. | I and IV |
C. | III and IV |
D. | I, III and IV |
Answer» B. I and IV |
65. |
Which of the following describes a handle (as applicable to LR-parsing) appropriately? |
A. | It is the position in a sentential form where the next shift or reduce operation will occur |
B. | It is non-terminal whose production will be used for reduction in the next step |
C. | It is a production that may be used for reduction in a future step along with a position in the sentential form where the next shift or reduce operation will occur |
D. | It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found |
Answer» D. It is the production p that will be used for reduction in the next step along with a position in the sentential form where the right hand side of the production may be found |
66. |
An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if |
A. | the SLR(1) parser for G has S-R conflicts |
B. | the LR(1) parser for G has S-R conflicts |
C. | the LR(0) parser for G has S-R conflicts |
D. | the LALR(1) parser for G has reduce-reduce conflicts |
Answer» B. the LR(1) parser for G has S-R conflicts |
67. |
Consider the following two statements:
|
A. | Both P and Q are true |
B. | P is true and Q is false |
C. | P is false and Q is true |
D. | Both P and Q are false |
Answer» C. P is false and Q is true |
68. |
Consider the following grammar.
|
A. | (i) and (ii) |
B. | (ii) and (iii) |
C. | (i) and (iii) |
D. | None of the above |
Answer» D. None of the above |
69. |
A canonical set of items is given below
|
A. | a shift-reduce conflict and a reduce-reduce conflict. |
B. | a shift-reduce conflict but not a reduce-reduce conflict. |
C. | a reduce-reduce conflict but not a shift-reduce conflict. |
D. | neither a shift-reduce nor a reduce-reduce conflict. |
Answer» D. neither a shift-reduce nor a reduce-reduce conflict. |
70. |
Consider the grammar defined by the following production rules, with two
|
A. | + is left associative, while ∗ is right associative |
B. | + is right associative, while ∗ is left associative |
C. | Both + and ∗ are right associative |
D. | Both + and ∗ are left associative |
Answer» B. + is right associative, while ∗ is left associative |
71. |
Consider the following grammar:
|
A. | {S → FR} and {R → ε } |
B. | {S → FR} and { } |
C. | {S → FR} and {R → *S} |
D. | {F → id} and {R → ε} |
Answer» A. {S → FR} and {R → ε } |
72. |
Consider the following translation scheme. S → ER R → *E{print("*");}R | ε E→ F + E {print("+");} | F F → (S) | id {print(id.value);} Here id is a token that represents an integer and id.value represents the corresponding integer value. For an input '2 * 3 + 4', this translation scheme prints |
A. | 2 * 3 + 4 |
B. | 2 * +3 4 |
C. | 2 3 * 4 + |
D. | 2 3 4+* |
Answer» D. 2 3 4+* |
73. |
The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the grammar is |
A. | ambiguous |
B. | left-recursive |
C. | right-recursive |
D. | an operator-grammar |
Answer» A. ambiguous |
74. |
Consider the grammar S → (S) | a Let the number of states in SLR(1), LR(1) and LALR(1) parsers for the grammar be n1, n2 and n3 respectively. The following relationship holds good |
A. | n1 < n2 < n3 |
B. | n1 = n3 < n2 |
C. | n1 = n2 = n3 |
D. | n1 ≥ n3 ≥ n2 |
Answer» B. n1 = n3 < n2 |
75. |
Consider the following expression grammar. The seman-tic rules for expression
|
A. | It detects recursion and eliminates recursion |
B. | It detects reduce-reduce conflict, and resolves |
C. | It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action |
D. | It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift action |
Answer» C. It detects shift-reduce conflict, and resolves the conflict in favor of a shift over a reduce action |
76. |
Which of the following grammar rules violate the requirements of an operator grammar ? P, Q, R are nonterminals, and r, s, t are terminals.
|
A. | 1 only |
B. | 1 and 3 only |
C. | 2 and 3 only |
D. | 3 and 4 only |
Answer» B. 1 and 3 only |
77. |
Consider the grammar with the following translation rules and E as the start symbol.
|
A. | 200 |
B. | 180 |
C. | 160 |
D. | 40 |
Answer» C. 160 |
78. |
Assume that the SLR parser for a grammar G has n1 states and the LALR parser for G has n2 states. The relationship between n1 and n2 is: |
A. | n1 is necessarily less than n2 |
B. | n1 is necessarily equal to n2 |
C. | n1 is necessarily greater than n2 |
D. | none of these |
Answer» B. n1 is necessarily equal to n2 |
79. |
Consider the grammar shown below S → i E t S S' | a S' → e S | ε E → b In the predictive parse table. M, of this grammar, the entries M[S', e] and M[S', $] respectively are |
A. | {S' → e S} and {S' → e} |
B. | {S' → e S} and {} |
C. | {S' → ε} and {S' → ε} |
D. | {S' → e S, S'→ ε} and {S' → ε} |
Answer» D. {S' → e S, S'→ ε} and {S' → ε} |
80. |
Consider the translation scheme shown below
|
A. | 9 + 5 + 2 |
B. | 9 5 + 2 + |
C. | 9 5 2 + + |
D. | + + 9 5 2 |
Answer» B. 9 5 + 2 + |
81. |
Which of the following is essential for converting an infix expression to the postfix from efficiently? |
A. | An operator stack |
B. | An operand stack |
C. | An operand stack and an operator stack |
D. | A parse tree |
Answer» A. An operator stack |
82. |
The grammar whose productions are
|
A. | a |
B. | b |
C. | c |
D. | d |
Answer» D. d |
83. |
Consider the following grammars
|
A. | Only (S1), (S2) and (S3), (S4) |
B. | Only (S1), (S3) and (S2), (S4) |
C. | Only (S2), (S3) and (S1), (S4) |
D. | None of the above |
Answer» B. Only (S1), (S3) and (S2), (S4) |
84. |
Which is True about SR and RR-conflict: |
A. | If there is no SR-conflict in CLR(1) then definitely there will be no SR-conflict in LALR(1). |
B. | RR-conflict might occur if lookahead for final items(reduce-moves) is same. |
C. | Known that CLR(1) has no RR-conflict, still RR-conflict might occur in LALR(1). |
D. | All of the above. |
Answer» D. All of the above. |
85. |
Which of the following statement(s) regarding a linker software is/are true ? I A function of a linker is to combine several object modules into a single load module. II A function of a linker is to replace absolute references in an object module by symbolic references to locations in other modules. |
A. | Only I |
B. | Only II |
C. | Both I and II |
D. | Neither I nor II |
Answer» A. Only I |
86. |
Shift-Reduce parsers perform the following: |
A. | Shift step that advances in the input stream by K(K > 1) symbols and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol. |
B. | Shift step that advances in the input stream by one symbol and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol. |
C. | Shift step that advances in the input stream by K(K = 2) symbols and Reduce step that applies a completed grammar rule to form a single tree |
D. | Shift step that does not advance in the input stream and Reduce step that applies a completed grammar rule to form a single tree. |
Answer» B. Shift step that advances in the input stream by one symbol and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol. |
87. |
Incremental-Compiler is a compiler |
A. | which is written in a language that is different from the source language |
B. | compiles the whole source code to generate object code afresh |
C. | compiles only those portion of source code that have been modified. |
D. | that runs on one machine but produces object code for another machine |
Answer» C. compiles only those portion of source code that have been modified. |
88. |
Which one of the following is FALSE? |
A. | A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end. |
B. | Available expression analysis can be used for common subexpression elimination. |
C. | Live variable analysis can be used for dead code elimination. |
D. | x = 4 ∗ 5 => x = 20 is an example of common subexpression elimination. |
Answer» D. x = 4 ∗ 5 => x = 20 is an example of common subexpression elimination. |
89. |
Consider the following C code segment.
|
A. | The code contains loop invariant computation |
B. | There is scope of common sub-expression elimination in this code |
C. | There is scope of strength reduction in this code |
D. | There is scope of dead code elimination in this code |
Answer» D. There is scope of dead code elimination in this code |
90. |
Consider the intermediate code given below:
|
A. | 5 and 7 |
B. | 6 and 7 |
C. | 5 and 5 |
D. | 7 and 8 |
Answer» B. 6 and 7 |
91. |
Consider the following code segment.
|
A. | 6 |
B. | 8 |
C. | 9 |
D. | 10 |
Answer» D. 10 |
92. |
A linker reads four modules whose lengths are 200, 800, 600 and 500 words respectively. If they are loaded in that order, what are the relocation constants? |
A. | 0, 200, 500, 600 |
B. | 0, 200, 1000, 1600 |
C. | 200, 500, 600, 800 |
D. | 200, 700, 1300, 2100 |
Answer» B. 0, 200, 1000, 1600 |
93. |
A language L allows declaration of arrays whose sizes are not known during compilation. It is required to make efficient use of memory. Which of the following is true? |
A. | A compiler using static memory allocation can be written for L |
B. | A compiler cannot be written for L, an interpreter must be used |
C. | A compiler using dynamic memory allocation can be written for L |
D. | None of the above |
Answer» C. A compiler using dynamic memory allocation can be written for L |
94. |
The expression (a*b)* c op........ where 'op' is one of '+', '*' and '↑' (exponentiation) can be evaluated on a CPU with a single register without storing the value of (a * b) if |
A. | ‘op’ is ‘+’ or ‘*’ |
B. | 'op’ is ‘↑’ or ‘*’ |
C. | 'op’ is ‘↑’ or ‘+’ |
D. | not possible to evaluate without storing |
Answer» A. ‘op’ is ‘+’ or ‘*’ |
95. |
Which of the following macros can put a micro assembler into an infinite loop?
|
A. | (ii) only |
B. | (i) only |
C. | Both (i) and (ii) |
D. | None of the above |
Answer» A. (ii) only |
96. |
Consider the following expression
|
A. | x1 = a - b y1 = p * c x2 = u * v y2 = p + q |
B. | x 1 = a - b y1 = x2 * c x3 = u * v y2 = x4 + y3 |
C. | x1 = a - b y2 = x1 * c x2 = u * v y3 = x2 + y2 |
D. | p = a - b q = p * c p = u * v q = p + q |
Answer» C. x1 = a - b y2 = x1 * c x2 = u * v y3 = x2 + y2 |
97. |
In multi-programmed systems, it is advantageous if some programs such as editors and compilers can be shared by several users. Which of the following must be true of multi-programmed systems in order that a single copy of a program can be shared by several users?
|
A. | I only |
B. | II only |
C. | Ill only |
D. | I, II and III |
Answer» C. Ill only |
Done Reading?