MCQOPTIONS
Saved Bookmarks
MCQOPTIONS
This section includes 42 Mcqs, each offering curated multiple-choice questions to sharpen your Computer Science Engineering (CSE) knowledge and support exam preparation. Choose a topic below to get started.
| 1. |
Consider the languagesL1={0^{i}1^{j}|i != j},L2={0^{i}1^{j}|i = j},L3 = {0^{i}1^{j}|i = 2j+1},L4 = {0^{i}1^{j}|i != 2j}.Which one of the following statements is true? |
| 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» E. | |
| 2. |
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» D. Recursively enumerable but not context free. | |
| 3. |
Consider the language L1,L2,L3 as given below.L1={0^{p}1^{q} | p,q in N}L2={0^{p}1^{q} | p,q in N and p=q} L3={0^{p}1^{q}1^{r} | p,q,r in N and p=q=r}Which of the following statements is NOT TRUE? |
| 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» D. Turing machine can be used to recognize all the three languages | |
| 4. |
Which of the following problems are decidable?1) Does a given program ever produce an output?2) If L is a context-free language, then is L (complement of L) also context-free?3) If L is a regular language, then is L also regular?4) If L is a recursive language, then, is L also recursive? |
| A. | 1, 2, 3, 4 |
| B. | 1, 2 |
| C. | 2, 3, 4 |
| D. | 3, 4 |
| Answer» E. | |
| 5. |
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» D. b*ab*ab | |
| 6. |
Consider the following two problems on undirected graphs: : Given G(V,E), does G have an independent set of size |v| 4? : Given G(V,E), does G have an independent set of size 5?Which one of the following is TRUE? |
| 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» C. Both and are NP-complete | |
| 7. |
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» C. Strings that begin and end with the same symbol | |
| 8. |
Consider the grammar with the following translation rules and E as the start symbol.E E1 # T { E.value = E1.value * T.value } | T{ E.value = T.value }T T1 & F { T.value = T1.value + F.value } | F{ T.value = F.value }F num { F.value = num.value }Compute E.value for the root of the parse tree for the expression: 2 # 3 & 5 # 6 & 4. |
| A. | 200 |
| B. | 180 |
| C. | 160 |
| D. | 40 |
| Answer» D. 40 | |
| 9. |
Which of the following grammar rules violate the requirements of an operator grammar ? P, Q, R are nonterminals, and r, s, t are terminals.1. P Q R2. P Q s R3. P 4. P Q t R r |
| A. | 1 only |
| B. | 1 and 3 only |
| C. | 2 and 3 only |
| D. | 3 and 4 only |
| Answer» C. 2 and 3 only | |
| 10. |
Consider the translation scheme shown belowS T RR + T {print ('+');} R | T num {print (num.val);}Here num is a token that represents an integer and num.val represents thecorresponding integer value. For an input string '9 + 5 + 2', this translation scheme willprint |
| A. | 9 + 5 + 2 |
| B. | 9 5 + 2 + |
| C. | 9 5 2 + + |
| D. | + + 9 5 2 |
| Answer» C. 9 5 2 + + | |
| 11. |
The grammar whose productions are if id then if id then else id := idis ambiguous becausea) the sentence if a then if b then c:= d has two parse treesb) the left most and right most derivations of the sentence if a then if b then c:= d give rise to different parse treesc) the sentence if a then if b then c:= d else c:= f has more than two parse treesd) the sentence if a then if b then c:= d else c:= f has two parse trees |
| A. | a |
| B. | b |
| C. | c |
| D. | d |
| Answer» E. | |
| 12. |
Consider the grammar defined by the following production rules, with twooperators and +S --> T * PT --> U | T * UP --> Q + P | QQ --> IdU --> IdWhich one of the following is TRUE? |
| 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» C. Both + and are right associative | |
| 13. |
Consider the following grammars(S1) :A --> aBCDB --> bc|cC --> d| D -> b(S2) :A --> aBCDB --> bc| C --> d|cD -> b(S3) :A --> aBCDB --> bc| C --> d| D -> b(S4) :A --> aBCDB --> bc|cC --> d|cD -> bWhich of the following grammar has same follow set for variable B? |
| 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» C. Only (S2), (S3) and (S1), (S4) | |
| 14. |
Consider the following C code segment.for (i = 0, i |
| 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» E. | |
| 15. |
Consider the following code segment.x = u - t;y = x * v;x = y + w;y = t - z;y = x * y;The minimum number of total variables required to convert the above code segment tostatic single assignment form is Note : This question was asked as Numerical AnswerType. |
| A. | 6 |
| B. | 8 |
| C. | 9 |
| D. | 10 |
| Answer» E. | |
| 16. |
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» E. | |
| 17. |
Consider the intermediate code given below:1. i = 12. j = 13. t1 = 5 * i4. t2 = t1 + j5. t3 = 4 * t26. t4 = t37. a[t4] = 18. j = j + 19. if j |
| A. | 5 and 7 |
| B. | 6 and 7 |
| C. | 5 and 5 |
| D. | 7 and 8 |
| Answer» C. 5 and 5 | |
| 18. |
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» B. left-recursive | |
| 19. |
Which of the following macros can put a micro assembler into an infinite loop?(i).MACRO M1 X.IF EQ, X ;if X=0 thenM1 X + 1.ENDC.IF NE X ;IF X 0 then.WORD X ;address (X) is storedhere.ENDC.ENDM(ii).MACRO M2 X.IF EQ XM2 X.ENDC.IF NE, X.WORD X+1.ENDC.ENDM |
| A. | (ii) only |
| B. | (i) only |
| C. | Both (i) and (ii) |
| D. | None of the above |
| Answer» B. (i) only | |
| 20. |
Consider the following expressionu*v+a-b*cWhich one of the following corresponds to a static single assignment from the above expressions |
| 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» D. p = a - b q = p * c p = u * v q = p + q | |
| 21. |
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 rulesS --> aB S --> bAB --> b A --> aB --> bS A --> aSB --> aBB A --> bAAWhich of the following strings is generated by the grammar? |
| A. | aaaabb |
| B. | aabbbb |
| C. | aabbab |
| D. | abbbba |
| Answer» D. abbbba | |
| 22. |
Consider the following grammar:S FRR S | F idIn the predictive parser table, M, of the grammar the entries M[S, id] and M[R, $]respectively. |
| A. | {S FR} and {R } |
| B. | {S FR} and { } |
| C. | {S FR} and {R *S} |
| D. | {F id} and {R } |
| Answer» B. {S FR} and { } | |
| 23. |
A canonical set of items is given belowS --> L. > RQ --> R.On input symbol < the set has |
| 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» E. | |
| 24. |
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» C. the LR(0) parser for G has S-R conflicts | |
| 25. |
Consider the following statements related to compiler construction :I. Lexical Analysis is specified by context-free grammars and implemented by pushdown automata.II. Syntax Analysis is specified by regular expressions and implemented by finite-state machine. Which of the above statement(s) is/are correct? |
| A. | Only I |
| B. | Only II |
| C. | Both I and II |
| D. | Neither I nor II |
| Answer» E. | |
| 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» D. The set of all strings that begin and end with either 0 or 1. | |
| 27. |
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» D. 21 | |
| 28. |
Consider the following two statements:P: Every regular grammar is LL(1)Q: Every regular set has a LR(1) grammarWhich of the following is TRUE? |
| 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» D. Both P and Q are false | |
| 29. |
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» E. | |
| 30. |
Which of the following are decidable ?1. whether the intersection of two regular language is infinite.2. whether a give context free language is regular3. whether two push down automata accept the same language.4. whether a given grammar is context free |
| A. | 1 and 2 |
| B. | 1 and 4 |
| C. | 2 and 3 |
| D. | 2 and 4 |
| Answer» C. 2 and 3 | |
| 31. |
Match all items in Group 1 with correct options from those given in Group 2.List I List IIP. Regular Expression 1. Syntax analysisQ. Push down automata 2. Code GenerationR. Dataflow analysis 3. Lexical analysisS. Register allocation 4. Code optimization |
| 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» C. P-3, Q-4, R-1, S-2 | |
| 32. |
Consider the following grammar.S -> S * ES -> EE -> F + EE -> FF -> idConsider the following LR(0) items corresponding to the grammar above.(i) S -> S * .E(ii) E -> F. + E(iii) E -> F + .EGiven the items above, which two of them will appear in the same set in the canonicalsets-of-items for the grammar? |
| A. | (i) and (ii) |
| B. | (ii) and (iii) |
| C. | (i) and (iii) |
| D. | None of the above |
| Answer» E. | |
| 33. |
Consider the following two sets of LR(1) items of an LR(1) grammar.X -> c.X, c/dX -> .cX, c/dX -> .d, c/dX -> c.X, $X -> .cX, $X -> .d, $Which of the following statements related to merging of the two sets in thecorresponding LALR parser is/are FALSE?1. Cannot be merged since look aheads are different.2. Can be merged but will result in S-R conflict.3. Can be merged but will result in R-R conflict.4. Cannot be merged since goto on c will lead to two different sets. |
| A. | 1 only |
| B. | 2 only |
| C. | 1 and 4 only |
| D. | 1, 2, 3, and 4 |
| Answer» E. | |
| 34. |
Consider the following expression grammar. The seman-tic rules for expressioncalculation are stated next to each grammar production.E number E.val = number. val| E '+' E E(1).val = E(2).val + E(3).val| E ' ' E E(1).val = E(2).val E(3).valThe above grammar and the semantic rules are fed to a yacc tool (which is an LALR (1)parser generator) for parsing and evaluating arithmetic expressions. Which one of thefollowing is true about the action of yacc for the given grammar? |
| 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» D. It detects shift-reduce conflict, and resolves the conflict in favor of a reduce over a shift action | |
| 35. |
Consider the following context free languages:L1 = {0^i 1^j 2^k | i+j = k}L2 = {0^i 1^j 2^k | i = j or j = k}L3 = {0^i 1^j | i = 2j+1}Which of the following option is true? |
| 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» D. None of the above | |
| 36. |
Which of the following are decidable?I. Whether the intersection of two regular languages is infiniteII. Whether a given context-free language is regularIII. Whether two push-down automata accept the same languageIV. Whether a given grammar is context-free |
| A. | I and II |
| B. | I and IV |
| C. | II and III |
| D. | II and IV |
| Answer» C. II and III | |
| 37. |
Consider the following decision problems: (P1) Does a given finite state machine accept a given string (P2) Does a given context free grammar generate an infinite number of stings Which of the following statements is true? |
| 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» B. Neither (P1) nor (P2) are decidable | |
| 38. |
Consider the following two statements:S1: { 0^2n |n >= l} is a regu1ar languageS2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar languageWhich of the following statements is correct? |
| 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» D. None of S1 and S2 is correct | |
| 39. |
Which of the following statements are TRUE?I. There exist parsing algorithms for some programming languages whose complexities are less than O(n3).II. A programming language which allows recursion can be implemented with static storage allocation.III. No L-attributed definition can be evaluated in the framework of bottom-up parsing.IV. Code improving transformations can be performed at both source language and intermediate code level. |
| A. | I and II |
| B. | I and IV |
| C. | III and IV |
| D. | I, III and IV |
| Answer» C. III and IV | |
| 40. |
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» B. Only II | |
| 41. |
Consider the following statements:(I) The output of a lexical analyzer is groups of characters.(II) Total number of tokens in printf("i=%d, &i=%x", i, &i); are 11.(III) Symbol table can be implementation by using array and hash table but not tree.Which of the following statement(s) is/are correct? |
| A. | Only (I) |
| B. | Only (II) and (III) |
| C. | All (I), (II), and (III) |
| D. | None of these |
| Answer» E. | |
| 42. |
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?I. The program is a macroII. The program is recursiveIII.The program is reentrant |
| A. | I only |
| B. | II only |
| C. | Ill only |
| D. | I, II and III |
| Answer» D. I, II and III | |