Compiler Design & TOC Test - 4 - PDF Flipbook

428 Views
56 Downloads
PDF 3,044,765 Bytes

Download as PDF

REPORT DMCA

---

GATE
CSE

CompilerDesign
+

TheoryofComputation

Test-04Solutions

COMPILER DESIGN + THEORY OF COMPUTATION
1. Consider the grammar

S → PQ | SQ | PS
P→x
Q→y
To get a string of n terminals, the number of productions to be
used is
a) n2
b) n + 1
c) 2n
d) 2n – 1
Answer: (d)
2. Consider the following statements

I. The complement of every Turing decidable language is
Turing decidable

II. There exists some language which is in NP but is not
Turing decidable

III. If L is a language in NP, L is Turing decidable
Which of the above statements is/are true?
a) Only I
b) Only III
c) Only I and II
d) Only I and III
Answer: (d)

1

3. Let L be the language represented by the regular expression
∑2:*00112:* Where I: ∑ = /0,11- What is the minimum number
of states in a DFA that recognizes L (complement of ‘L’) ?
a) 4
b) 5
c) 6
d) 8
Answer: (b)

4. Which one of the following is TRUE?
a) The language L = Ian bn I n ~ 0 I is regular.
b) The language L = Ian I n is prime} is regular.
c) The language L = Iw Iw has 3k + 1b's for some kEN with L =
[c, bll is regular.
d) The language
Answer: (c)

5. Which one of the following problems is undecidable?
a) Deciding if a given context-free grammar is ambiguous.
b) Deciding if a given string is generated by a given context-free
grammar.
c) Deciding if the language generated by a given context-free
grammar is empty.
d) Deciding if the language generated by a given context-free
grammar is finite.
Answer: (a)

2

6. Which of the following statements is/are FALSE?
1. For every non-deterministic Turing machine, there exists an
equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union and
complementation. Theory of Computation
3. Turing decidable languages are closed under intersection and
complementation.
4. Turing recognizable languages are closed under union and
intersection.
a) 1 and 4 only
b) 1 and 3 only
c) 2 only
d) 3 only
Answer: (a)

7. Consider the DFAA given below.

Which of the following are FALSE?
1. Complement of VA) 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 to, 11 of length at lea. 2.
a) 1 and 3 only

3

b) 2 and 4 only
c) 2 and 3 only
d) 3 and 4 only
Answer: (d)
8. Which of the following is/are undecidable?
1. G is a CFG. is L(G) = < D?
2. G is a CFG. is L(G) = L:*?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?
a) 3 only
b) 3 and 4 only
c) 1, 2 and 3 only
d) 2 and 3 only
Answer: (d)
9. Given the language L = lab, aa, baa!, which of the following
strings are in L*?
1. abaabaaabaa
2. aaaabaaaa
3. baaaaabaaaab
4. baaaaaba
a) 1, 2 and 3
b) 2, 3 and 4
c) 1, 2 and 4
d) 1, 3 and 4
Answer: (c)

4

10. Consider a random variable X that takes values +1 and –1 with
probability 0.5 each. The values of the cumulative distribution
function F(x) at x = –1 and + 1 are
a) 0 and 0.5
b) 0 and 1
c) 0.5 and 1
d) 0.25 and 0.75
Answer: (c)

11. What is the complement of the language accepted by the NFA
shown below? Assume E = {al and e is the empty string.

a)
b) { }
c) a
d) {a, }
Answer: (b)
12. Let P be a regular language and Q be a context free language
such that Q ~ P. (For example, let P be the language represented
by the regular expression p*q* and Q be [pnqn I n E NJ. Then
which of the following is ALWAYS regular?
a) P ∩Q
b) P – Q
c) ∑* – P
d) ∑* – Q

5

Answerer: (c)
13. 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)
14. Which of the following pairs have DIFFERENT expressive
power?
a) Deterministic finite automata (DFA) and Nondeterministic

finite automata (NFA)
b) Deterministic push down automata (DPDA) and Non-

deterministic push down automata (NPDA)
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)
15. 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 enumerable
c) L2 ∩L3 is recursively enumerable

6

d) L2 ∪L3 is recursively enumerable
Answer: (b)
16. Let L = | w E (0 + 1)* | w has even number of Is], i.e., L is the
set of all bit strings with even number of Is. 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)
17. Let w be any string of length n in 10, 11*. 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)
18. 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.

7

Answer: (b)
19. Which one of the following languages over the alphabet 10, 11

is described by the regular Expression (0 + 1)*0(0 + 1) * 0(0 +
1)*?
a) The Set of at! strings containing the Sub String 00
b) The set of all strings containing at most two O's.
c) The set of all strings containing at least two O's.
d) The et of all strings that begin and end with either 0 or 1.
Answer: (c)
20. Which one of the following is FALSE?

a) There is a 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)
21. In the following figure, DFA accepts the set of all strings over
{0, 1} that

a) Begin either with 0 or 1.
b) End with O.
c) End with 00.

8

d) Contain the substring Out
Answer: (c)
22. Which of the following is true for the language |aP| p is a
prime}?
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: (b)
23. 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
a) I and II
b) I and IV
c) II and III
d) II and IV.
Answer: (c)
24. If Land L are recursively enumerable, then � is
a) regular
b) context-free
c) context-sensitive
d) recursive

9

Answer: (c)
25. Which of the following statements 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)
26. Which of the following statements are true?
I. Every left-recursive grammar can be converted to a right-

recursive grammar and vice-versa
II. All s-productions can be removed from any context-free

grammar by suitable transformations
III. The language generated by a context-free grammar all of

whose productions are of the form X ~ w or X ~ wY
(where, w is a string of terminals and Yis a non-terminal),
is always regular
IV. The derivation trees of strings generated by a context-free
grammar in Chomsky Normal From are always binary trees
a) I, II, III and IV
b) II, III and IV only
c) I, III and IV only
d) I, II and IV only
Answer: (c)

10

27. Which of the following problems is undecidable?
a) Membership problem for CFGs.
b) Ambiguity problem for CFGs.
c) Finiteness problem for FSAs
d) (Equivalence problem for FSAs
Answer: (b)

28. Which of the following is TRUE?
a) Every subset of a regular set is regular
b) Every finite subset of a non-regular set is regular
c) The union of two non-regular sets is not regular
d) Infinite union off mite sets is regular
Answer: (b)

29. Let S be an NP-complete problem Q and R be two other
problems not known to be in NP. Q is polynomial-time
reducible to Sand S is polynomial-time reducible to R. Which of
the following statements is true?
a) R is NP-complete
b) R is NP-hard
c) Q is NP-complete
d) Q is NP-hard
Answer: (c)

11

30. Consider the regular language L = (111 + 11111)*. The
minimum number of states in any DFA accepting this languages
is
a) 3
b) 5
c) 8
d) 9
Answer: (d)

12