Compiler Design & TOC Test - 2 - PDF Flipbook

Compiler Design & TOC Test - 2

299 Views
25 Downloads
PDF 6,425,817 Bytes

Download as PDF

REPORT DMCA


GATE
CSE

CompilerDesign
+

TheoryofComputation

Test-02Solutions


COMPILER DESIGN + THEORY OF COMPUTATION
1. If s is a string over (0+l)* then let n0(s) denote the number of 0's

in s and n1(s) the number of 1's in s. Which one of the following
languages is not regular?
a) L = {s  (0 + l)* | n0(s) is a 3-digit prime}
b) L = {s  (0 + 1)*| for every prefix s' of s, | no(s') – n1(s')|≤ 2}
c) L = {s  (0 + l)* | n0(s)- n1(s) | ≤ 4}
d) L = {s  (0 + l)* | n0(s) mod 7 = n1(s)mod 5 = 0}
Answer: (c)
Solution:
a) is a finite language and every finite language is regular.
b) is an infinite language but we need to take prefixes apart
from comparing from 0's and l's hence we can construct the
DFA for this language, and it is regular.
d) is also the language accepted by a DFA with 35 states hence
it is regular.
2. Let L = {w∈ (0 + 1)*|w has even number of 1's}, i.e L is the set
of all bit strings with even number of 1's' Which one of the
regular expressions below represents L?
a) (0*10*1)*
b) 0*(10*10*)*
c) 0*(10*1)*0*
d) 0*1(10*1)*10*
Answer: (b)

1


Solution:
We can eliminate choice (d) immediately. Consider 111, it is in
(d), but the string has an odd number of 1's.
Consider the strings 1010101. This cannot be matched by
regular expression (c). So this can be eliminated.
Consider the string 01010. This cannot be matched by regular
expression (a).
So by elimination the choice is (b).
3. Which of the following statement is false?
a) Every NFA can be converted to an equivalent DFA
b) Every non-deterministic Turing machine can be converted to

an equivalent deterministic Turing machine.
c) Every regular language is also a context-free language
d) Every subset of a recursively enumerable set is recursive.
Answer: (d)
Solution:
Consider the set Σ*. Σ* is regular & R.E.
All the R.E sets are subsets of Σ*. All the R.E sets that are not
recursive are subsets of Σ*.
So the statement (d) is false.
Case (a): By the algorithm for the construction of the subset
machine every NFA can be converted to an equivalent DFA.
Case (b): start with a NDTM. Enumerate sequential numbers to
be base k where k represents the moves of the NDTM. Simulate

2


the sequence of moves with a DTM. We see NDTMs are
equivalent to DTMs.
Case (c): Trivially every regular set is a CFG. Just ignore the
stack in PDA to accept regular sets.
4. A deterministic finite automation (DFA) D with alphabet Σ =
{a, b} is given below

Which of the following finite state machine is a valid minimal
DFA which accepts the same language as D?

a)

b)

c)

3


d)
Answer: (a)
Solution:
s and t are equal states, Merge these states into a single state.
Then we get the FA as in the case of (a)
5. Match the following List – I with List – II
List - I
(E) Checking that identifiers are declared before their use
(F) Number of formal parameters in the declaration of a

function agrees with the number of actual parameters in a
use of that function
(G) Arithmetic expressions with matched pairs of parentheses
(H) Palindromes
List - II
(P) L = {an bm cn | n ≥ 1, m ≥ 1}
(Q) X → XbX | XcX | d X f | g
(R) L = {wcw | w (a|b)*}
(S) X → bXb | cXc |
Codes:
a) E – P, F – R, G – Q, H – S
b) E – R, F – P, G – S, H – Q

4


c) E – R, F – P, G – Q, H – S
d) E – P, F – R, G – S, H – Q
Answer: (c)
Solution:
P: L = {an bm cn | n ≥ 1, m ≥ 1} to check the actual and formal
parameters
Q: X → XbX | XcX | d X f |g generates the arithmetic
expressions with matched pairs of parentheses.
R: L = {wcw | w (a|b)*} to check the declaration of variable
before usage.
S: X → bXb | cXc | to generate palindromes.
6. Consider the following context-free grammars:
G1: S → aS|B, B → b|bB
G2: S → aA|bB, A→ aA|B|ε, B → bB|ε
Which one of the following pairs of languages is generated by
G1 and G2, respectively?
a) {am, bn| m > 0 or n > 0} and (am bn| m > 0 and n > 0}
b) {am, bn| m > 0 and n > 0} and (am bn| m > 0 or n ≥ 0}
c) {am, bn| m ≥ 0 or n > 0} and (am bn| m > 0 and n > 0}
d) {am, bn| m ≥ 0 or n > 0} and (am bn| m > 0 or n > 0}
Answer: (d)
Solution:
G1: S→ aS|B

B→ b|bB
⟹B → b+

5


S→ aS| b+
S→ a*b+ = {am bn | m ≥ 0, n ≥ 0}
G2: S→ aA| bB
A → aA |B|
B→ bB| B →b*
A → aA| b*|
A → a*|b*|a*
A → a*|b*|a*
A → a* b*
S → aa* b*|bb*
S → a+b*|b+
L = {am bn |m ≥ 0, n ≥ 0,} ∪ { bn |n > 0}
7. 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) un-decidable but recursively enumerable
c) un-decidable and not recursively enumerable
d) decidable but not recursively enumerable
Answer: (b)
Solution:
L is RES but un-decidable. It is un-decidable if a TM will ever
halt and accept anything at all

6


8. Consider the following languages.
L1 = {< M > | M takes at least 2016 steps on some input),
L2 = {< M > | M takes at least 2016 steps on all inputs) and
L3 = {< M > | M accepts },
Where for each Turing machine M, < M > denotes a specific
encoding of M.
Which one of the following is TRUE?
a) L1 is recursive and L2, L3 are not recursive
b) L2 is recursive and L1, L3 are not recursive
c) L1, L2 are recursive and L3 is not recursive
d) L1, L2, L3 are recursive
Answer: (c)
Solution:
L1 is Recursive
L2 is Recursive
L3 is Not Recursive

9. L1 is a recursively enumerable language over Σ. An algorithm A
effectively enumerates its words as w1, w2, w3, .... Define
another language L2 over Σ ∪{#} as {wi # wj: wi, wj∈ L1, i < j}.
Here # is a new symbol. Consider the following assertions:
S1: L1 is recursive implies L2 is recursive
S2: L2 is recursive implies L1 is recursive
Which of the following statements is true?
a) Both S1 and S2 are true
b) S1 is true but S2 is not necessarily true

7


c) S2 is true but S1 is not necessarily true
d) Neither is necessarily true
Answer: (b)
10. Which of the following decision problems are un-decidable?

I. Given NFAs N1 and N2, is L(N1)∩L(N2) = ϕ?

II. Given a CFG G = (N, ∑*, does x  L(G)?
III. Given CFGs G1 is L(G1) = L(G2)?
IV. Given a TM M, is L(M) = ϕ?
a) I and IV only
b) II and III only
c) III and IV only
d) II and IV only
Answer: (c)
Solution:
III. Equality of CFG is un-decidable
IV. Emptiness of TM is un-decidable
11. Which of the regular expression given below represent the
following DFA?

I. 0*1(1+00*1)*
II. 0*1*1+11*0*1
III. (0+1)*1

8


a) I and II only
b) I and III only
c) II and III only
d) I, II, and III.
Answer: (b)
Solution:

0*1 - Accepted
(1 + 00*1)* - Accepted
(i) 0*1(1 + 00*1)* is also accepted.
Again

(0 + 121*0)*11*
∴0*1+0

( + 1+)0 = 1*0
(iii) (1*0)* 1+ = (0 + 1)*1
∴ 0*1(1 + 00*1)* and (0 + 1)*1 are equal and accepted by given
FA
We will use the method of elimination.
Consider the string 1010. This is accepted by the DFA.
1010∉0*1*1*

9


1010∉1*0*1
So, ‘II’ cannot be the answer So, the answer is (b).
12. Consider the set of strings on {0, 1} in which, every sub string
of 3 symbols has at most two zeros. For example, 001110 and
011001 are in the language, but 100010 is not. A11 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)

b)

10


c)

d)
Answer: (d)
Solution:
L = {A1l the strings of 0's and l's where every substring of 3
symbols has at most 2 zero's)
Case 1: If we go with option (a)

If we take the substring 0000, it has a substring 000 containing
more than 2 zero's so it is invalid string but it is accepted by
DFA. Hence this option is not possible.

11


Case 2: If we go with option (b).

w = 000 is a string and has a substring 000 having more than
2 zero's. Not in a language but it is accepted. So option (b) is
not possible.
Case 3: If we go with option (c)

w = 001000 has a substring 000 having more than 2 zero's and
accepted but it is not in the given language.

12


Case (4): If we go with option (d)

This machine accepts all the strings were every substring of 3
symbols has at most 2 zero's.
So this is the correct option
13. Consider the DFA A given below.

Which of the following are FALSE?
1. Complement of L(A) is context – free.
2. L(A) = L((11*0 + 0)(0 + 1)*0*1*)
3. For the language accepted by A, A is the minimal DFA.
4. A accepts all strings over {0, 1} of length at least 2.
a) 1 and 3 only
b) 2 and 4 only
c) 2 and 3 only
d) 3 and 4 only

13


Answer: (d)
Solution:
The given DFA can be minimized into 2 states and abc
accepts the strings of length l. So (3) and (4) are FALSE
14. Which one of the following is not decidable?
a) Given a Turing machine M, a string s and an integer k, M

accepts s within k steps
b) Equivalence of two given Turing machines
c) Language accepted by a given finite state machine is non

empty
d) Language generated by a context free grammar is non

empty.
Answer: (b)
Solution:
Case (a):
Just run the TMs for k steps with string s as input we will
know in a finite amount of time whether the string is accepted
So this is decidable.
Case (b):
By Rice's theorem every non-trivial property of TMs is not
decidable. So the equivalence of TMs is not decidable.
Case(c):
The emptiness problem of regular sets is decidable. Just check
for strings of length 0, 1, 2, ......., n, if they are accepted' Here n
is the number of state of finite automata.

14


Case (d):
The emptiness Problem of CFG is decidable.
15. Consider the alphabet Σ = {0, l}, the null/empty string , and

the set of strings X0, X1, and X2 generated by the
corresponding non-terminals of a regular grammar X0, X1,
and X2 are related as follows.
X0 = 1 X1
X1 = 0 X1 + 1X2
X2 = 0 X1 + { }
Which one of the following choices precisely represents the
strings in X0?
a) 10(0* + (10)*1
b) 10(0* + (10*))*1
c) 1(0 + 10)*1
d) 10(0 +10)*1 + 110(0 + 10)*1
Answer: (c)
Solution:
X0 = 1 X1
X1 = 0 X1 + 1 X2
X2 = 0 X1 + { }
So X1 = 1
X1 = 11, = 11 should be in the answer
Only (c) satisfies.
Consider the FA formed from the regular expression
equations

15


We must trace a path between X0 & F. To reach X1 we need
a l, to stay in X1 we need (0 + 10)* to reach X2 we need a l.
So we need 1(0 + 10)*1

Alternatively
By grammar
X0 → 1X1
X1 → 0X1 |1X2
X2 → 0X1|
We have

16. Let M = (K, Σ, F, ∆, s, F) be a Pushdown automaton.
Where K={s,f}, F= {f}
∑ = {A, B}, f = [A} AND
∆ = {((s, a, ε), (s, a)), ((s, b, ε) (s, a)), ((s, a, ε), (f, ε)), ((f, a, a),
(f, ε)), ((f, b, a), (f, ε))}
Which one of the following strings is not a member of L (M)?
a) aaa
b) aabab

16


c) baaba
d) bab
Answer: (c)
Solution:
The string baaba is not a member of a language as it is not
accepted by the given PDA.
17. In which of the cases stated below is the following statement
true?
"For every nondeterministic machine M1 there exists an
equivalent deterministic machine M2 recognizing the same
language".
a) M1 is nondeterministic finite automation
b) M1, is a nondeterministic PDA
c) M1 is a nondeterministic Turing machine
d) For no machine M1 use the above statement true.
Answer: (a)
Solution:
The regular sets which are accepted by NFA are also accepted
by equivalent DFA' The R.E sets which are accepted by
deterministic TM are also accepted by nondeterministic TM.
However deterministic and non-deterministic PDA are not
equivalent. The language of all palindromes over an alphabet is
the example of a language that is accepted by a DPDA but not
a NPDA.

17


18. Let L be a language and � be its complement. Which one of
the following is NOT a viable possibility?
a) Neither L nor � is recursively enumerable (r.e).
b) One of L and � is r.e. but not recursive; the other is not r.e.
c) Both L and � are r.e. but not recursive.
d) Both L and � are recursive.
Answer: (c)
Solution:

L be a language
� be the complement of L
If L is RES but � need not be RES.
So both L and � are RS but RES is not possible.
19. A single tape Turing Machine M has two states q0 and q1 of
which q0 is the starting state. The tape alphabet of M is {0, 1,
B} and its input alphabet is {0, 1}. The symbol B is the blank
symbol used to indicate end of an input string. The transition
function of M is described in the following table.

18


The table is interpreted as illustrated below. The entry (q1, 1, R)
in row q0 and column I signifies that if M is in state q0 and
reads 1 on the current tape square, then it writes 1 on the same
tape square, moves its tape head one position to the right and
transitions to state q1 Which of the following statements is true
about M?
a) M does not halt on any string in (0 + 1)+
b) M does not halt on any string in (00 + 1)*
c) M halts on all string ending in a 0
d) M halts on all string ending in a 1
Answer: (a)
Solution:
We will use the method of elimination. If the input is , Then
(q0, B) = HALT. So case (b) is false.
Let the input be 1, then

The machine is in loop. So case (d) is false.
Let the input be 00
The machine does not halt.
So (c) is false.

19


20. The regular grammar for the language L={W| na (w)and na
(w)are both even, w ϵ {a, b} *} is given by: (Assume, p, q, r
and s are states)
a) P →aq| br| λ, q → bs |ap
r → as| bp, s→ ar |bq, p and S are initial and final states
b) P →aq |br, q →bs |ap
r → as| bp, S→ ar |bq, P and S are initial and final states.
c) P→ aq |br |λ, q →bs |ap
r→ as| bp, s→ ar| bq, p is both initial and final states
d) P→ aq| br|, q →bs |ap
r→ as| bp, s→ ar| bq, p is both initial and final states
Answer: (c)
Solution:
P→ aA|bR|
Q→ bS|aP
R→ aS|ph
A→ aR|pQ
Where ‘p’ is the initial state and final state
The machine will be

20


Note that option (a) is same grammar but it’s wrong because in
this choice it is given that both ‘p’ and ‘S’ are initial and final
states.
21. Which of the following derivations does a top-down parser use
while parsing an input string? The input is scanned from left to
right.
a) Left most derivation
b) Leftmost derivation traced out in revers
c) Rightmost derivation traced out in reverse
d) Rightmost derivation
Answer: (a)
Solution:
Top-down parsing can be viewed as attempt to find left-,most
derivations of an input stream by searching for parse trees using
top down expression of the given formal grammar rules.
22. In the context of compiler design “reduction in strength" refers
to
a) code optimization obtained by the use of cheaper machine

instructions
b) reduction in accuracy of the output

21


c) reduction in the range of values of input variables
d) reduction in efficiency of the program
Answer: (a)
Solution:
Strength reduction is a compiler optimization where expensive
operations are replaces with equivalent but less expensive
operations.
23. Which of the following strings is in the language defined by
grammar
S → 0A, A→1Al0Al1
a) 01100
b) 00101
c) 10011
d) 11111
Answer: (b)
Solution:
Language of given grammar is set of strings those starting with
0 and end with 1.
24. Given the following two languages:

L1 = {an bn| n ≥ 1} ∪{a}
L2 = {WC WR |w  {a, b}*}
Which statement is correct?
a) Both L1 and L2 are not deterministic.
b) L1 is not deterministic and L2 is deterministic
c) L1 is deterministic and L2 is not deterministic

22


d) Both L1, and, L2 are deterministic.
Answer: (d)
Solution:
We can find middle element of both given to pop out or
matching so, both L1 and L2 are deterministic content free
language but not regular.
25. Which of the following is FALSE?

The grammar S + aS| aSbS| ϵ, where S is the only non-
terminal symbol, and e is the null string, is ambiguous.
a) An unambiguous grammar has same left most and right

most derivation.
b) An ambiguous grammar can never be LR(k) for any k.
c) Recursive descent parser is a top down parser
Answer: (b)
Solution:
a. True, since grammar has more than one parse tree for string

w=aaa.
b. False, since if a grammar has more than one leftmost

derivation for a single sentential form the grammar is
ambiguous, but leftmost and right most derivation for a
sentential from may differ, even in an unambiguous
grammar.
Also, both option (c) and (d) are true.

23


26. The Servlet Response interface enables a servlet to formulate a
response for a client using the method
a) void log (Exception e, String s)
b) void destroy ()
c) int get Server Port ()
d) void set Context Type (String type)
Answer: (a)
Solution:
The Servlet Response object enables the servlet to formulate a
response for the client using the method get server name () get
writer (), and SetContentType ().

27. in the context of compiler design “reduction in strength" refers
to
a) code optimization obtained by the use of cheaper machine
instructions
b) reduction in accuracy of the output
c) reduction in the range of values of input variables
d) reduction in efficiency of the program
Answer: (a)
Solution:
Strength reduction is a compiler optimization where expensive
operations are replaced with equivalent but less expensive
operations.

24


28. in Java, when we implement an interface method, it must be
declared as:
a) Private
b) Protected
c) Public
d) Friend
Answer: (c)
Solution:
Interfaces are meant to define the public API of a type, and
only that, not its implementation. So, any method (or static
member) you define in an interface is by definition Public.

29. Which is the correct statement(s) for Non-Recursive predictive
parser?
S1: first (α) = {t|α ⇒ tβ for some string β}⇒tβ
S2: follow (x) = {a| S⇒α x aβ for some strings α and β}
a) Both statements S1 and S2 incorrect
b) S1 is incorrect and S2 is correct
c) S1 is correct and S2 is incorrect
d) Both statements S1 and S2 are correct
Answer:(d)
Solution:
We associate each grammar symbol A with the first (A). The
implementation of this set is that the grammar symbols A can in
some steps of transition produce the elements of the set first(A).

25


Grammar G. it can be defined as the set of terminals of grammar
G, which can immediately follow the non-terminal in a
production rule from start symbol.
Both statements are true.
30. A compiler for a high-level language that runs on one machine
and produces code for a different machine is called:
a) Optimizing
b) One pass compiler
c) Cross compiler
d) Multiphase compiler
Answer: (b)
Solution:
Peephole optimization is a kind of optimization performed over
a very small of instructions in segment of generated code. The
set is called a “peephole” or a “window”. It works by
recognizing sets of instructions that can be replace by shorter or
faster sets of instructions.
Common techniques applied in Peephole optimization is
constant folding that evaluate constant subexpressions in
advance.

26


Data Loading...