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?
Correct : B. 0*(10*10*)*
2. Consider the languages
L1={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?
Correct : 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?
Correct : 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
Correct : C. Context free but not regular
5. 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?
Correct : 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?
Correct : B. n+1
7. 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?
Correct : 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
Correct : D. D
9. Consider the following Finite State Automaton
The language accepted by this automaton is given by the regular expression
Correct : C. b*a(a+b)*
10. The minimum state automaton equivalent to the above FSA has the following number of states
Correct : B. 2
11. Which of the following languages is regular?
Correct : 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
Correct : 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
Correct : 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?
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?
Correct : 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?
Correct : 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?
Correct : 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?
Correct : B. L3 n L1 is recursive
19. Consider the regular language L =(111+11111)*. The minimum number of states
Correct : 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?
Correct : 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?
Correct : 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?
Correct : B. L1' is recursive and L2' is not recursively enumerable
23. 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?
Correct : 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?
Correct : 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
Correct : 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)*?
Correct : C. The set of all strings containing at least two 0’s.
27. Which one of the following is FALSE?
Correct : 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.
List I List II
P. Regular Expression 1. Syntax analysis
Q. Push down automata 2. Code Generation
R. Dataflow analysis 3. Lexical analysis
S. Register allocation 4. Code optimization
Correct : B. P-3, Q-1, R-4, S-2
29. Which of the following pairs have DIFFERENT expressive power?
Correct : 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?
Correct : C. S=T
31. Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?
Correct : B. L is regular but not O
32. Consider the following two statements:
S1: { 0^2n |n >= l} is a regu1ar language
S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar language
Which of the following statements is correct?
Correct : C. Both S1 and S2 are correct
33. Which of the following statements in true?
Correct : 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.
Correct : B. 2^N
35. Which of the following is true for the language {a^p} p is prine ?
Correct : D. It is neither regular nor context free but accepted by a turing machine
36. Which of the following are decidable ?
1. whether the intersection of two regular language is infinite.
2. whether a give context free language is regular
3. whether two push down automata accept the same language.
4. whether a given grammar is context free
Correct : B. 1 and 4
37. If L and L' are recursively enumerable, then L is
Correct : 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
S --> aB S --> bA
B --> b A --> a
B --> bS A --> aS
B --> aBB A --> bAA
Which of the following strings is generated by the grammar?
Correct : C. aabbab
39. 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?
Correct : C. L1, L3 can be recognized by Deterministic Push down automata
40. Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free
Correct : 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
Correct : 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?
Correct : C. P3 is undecidable if P2 is reducible to P3
43. 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?
Correct : A. Both (P1) and (P2) are decidable
44. Which of the following statements is false?
Correct : 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?
Correct : 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:
Correct : C. 10
47. The regular grammar for the language L = {anbm | n + m is even} is given by
Correct : 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?
Correct : 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?
Correct : D. L is regular
50. The number of tokens in the following C statement is (GATE 2000)
printf("i = %d, &i = %x", i, &i);
Correct : C. 10
51. In a compiler, keywords of a language are recognized during
Correct : 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?
Correct : A. Finite state automata
53. 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?
Correct : D. None of these
54. Which one of the following statements is FALSE?
Correct : 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?
Correct : D. T3T3
56. 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?
Correct : D. Neither I nor II
57. 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.
Correct : 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)?
Correct : D. b a a b
59. The number of tokens in the following C statement is printf("i=%d, &i=%x",
i&i);
Correct : 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?
Correct : B. Replace P * 32 by P < < 5
61. Debugger is a program that
Correct : 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.
X -> c.X, c/d
X -> .cX, c/d
X -> .d, c/d
X -> c.X, $
X -> .cX, $
X -> .d, $
Which of the following statements related to merging of the two sets in the
corresponding 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.
Correct : D. 1, 2, 3, and 4
63. The grammar S → aSa | bS | c is
Correct : C. Both LL(1)and LR(1)
64. 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.
Correct : B. I and IV
65. Which of the following describes a handle (as applicable to LR-parsing) appropriately?
Correct : 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
Correct : B. the LR(1) parser for G has S-R conflicts
67. Consider the following two statements:
P: Every regular grammar is LL(1)
Q: Every regular set has a LR(1) grammar
Which of the following is TRUE?
Correct : C. P is false and Q is true
68. Consider the following grammar.
S -> S * E
S -> E
E -> F + E
E -> F
F -> id
Consider the following LR(0) items corresponding to the grammar above.
(i) S -> S * .E
(ii) E -> F. + E
(iii) E -> F + .E
Given the items above, which two of them will appear in the same set in the canonical
sets-of-items for the grammar?
Correct : D. None of the above
69. A canonical set of items is given below
S --> L. > R
Q --> R.
On input symbol < the set has
Correct : D. neither a shift-reduce nor a reduce-reduce conflict.
70. Consider the grammar defined by the following production rules, with two
operators ∗ and +
S --> T * P
T --> U | T * U
P --> Q + P | Q
Q --> Id
U --> Id
Which one of the following is TRUE?
Correct : B. + is right associative, while ∗ is left associative
71. Consider the following grammar:
S → FR
R → S | ε
F → id
In the predictive parser table, M, of the grammar the entries M[S, id] and M[R, $]
respectively.
Correct : 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
Correct : D. 2 3 4+*
73. The grammar A → AA | (A) | ε is not suitable for predictive-parsing because the
grammar is
Correct : 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
Correct : B. n1 = n3 < n2
75. Consider the following expression grammar. The seman-tic rules for expression
calculation 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).val
The 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 the
following is true about the action of yacc for the given grammar?
Correct : 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.
1. P → Q R
2. P → Q s R
3. P → ε
4. P → Q t R r
Correct : B. 1 and 3 only
77. 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.
Correct : 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:
Correct : 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
Correct : D. {S' → e S, S'→ ε} and {S' → ε}
80. Consider the translation scheme shown below
S → T R
R → + T {print ('+');} R | ε
T → num {print (num.val);}
Here num is a token that represents an integer and num.val represents the
corresponding integer value. For an input string '9 + 5 + 2', this translation scheme will
print
Correct : B. 9 5 + 2 +
81. Which of the following is essential for converting an infix expression to the postfix from efficiently?
Correct : A. An operator stack
82. The grammar whose productions are
<stmt> → if id then <stmt>
<stmt> → if id then <stmt> else <stmt>
<stmt> → id := id
is ambiguous because
a) the sentence if a then if b then c:= d has two parse trees
b) the left most and right most derivations of the sentence if a then if b then c:= d give rise to different parse trees
c) the sentence if a then if b then c:= d else c:= f has more than two parse trees
d) the sentence if a then if b then c:= d else c:= f has two parse trees
Correct : D. d
83. Consider the following grammars
(S1) :
A --> aBCD
B --> bc|c
C --> d|∈
D -> b
(S2) :
A --> aBCD
B --> bc|∈
C --> d|c
D -> b
(S3) :
A --> aBCD
B --> bc|∈
C --> d|∈
D -> b
(S4) :
A --> aBCD
B --> bc|c
C --> d|c
D -> b
Which of the following grammar has same follow set for variable B?
Correct : B. Only (S1), (S3) and (S2), (S4)
84. Which is True about SR and RR-conflict:
Correct : 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.
Correct : A. Only I
86. Shift-Reduce parsers perform the following:
Correct : 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
Correct : C. compiles only those portion of source code that have been modified.
88. Which one of the following is FALSE?
Correct : D. x = 4 ∗ 5 => x = 20 is an example of common subexpression elimination.
89. Consider the following C code segment.
for (i = 0, i<n; i++)
{
for (j=0; j<n; j++)
{
if (i%2)
{
x += (4*j + 5*i);
y += (7 + 4*j);
}
}
}
Which one of the following is false?
Correct : D. There is scope of dead code elimination in this code
90. Consider the intermediate code given below:
1. i = 1
2. j = 1
3. t1 = 5 * i
4. t2 = t1 + j
5. t3 = 4 * t2
6. t4 = t3
7. a[t4] = –1
8. j = j + 1
9. if j <= 5 goto(3)
10. i = i + 1
11. if i < 5 goto(2)
The number of nodes and edges in the control-flow-graph constructed for the above
code, respectively, are
Correct : B. 6 and 7
91. 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 to
static single assignment form is Note : This question was asked as Numerical Answer
Type.
Correct : 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?
Correct : 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?
Correct : 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
Correct : A. ‘op’ is ‘+’ or ‘*’
95. Which of the following macros can put a micro assembler into an infinite loop?
(i)
.MACRO M1 X
.IF EQ, X ;if X=0 then
M1 X + 1
.ENDC
.IF NE X ;IF X≠0 then
.WORD X ;address (X) is stored
here
.ENDC
.ENDM
(ii)
.MACRO M2 X
.IF EQ X
M2 X
.ENDC
.IF NE, X
.WORD X+1
.ENDC
.ENDM
Correct : A. (ii) only
96. Consider the following expression
u*v+a-b*c
Which one of the following corresponds to a static single assignment from the above expressions
Correct : 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?
I. The program is a macro
II. The program is recursive
III.The program is reentrant