# Compiler Design & TOC Test - 3 - PDF Flipbook

Compiler Design & TOC Test - 3

219 Views
PDF 3,052,556 Bytes

GATE
CSE

CompilerDesign
+

TheoryofComputation

Test-03Solutions

COMPILER DESIGN + THEORY OF COMPUTATION
1. How many edges are there in a forest with v vertices and k

components?
a) (v + 1) – k
b) (v + 1)/2 – k
c) v – k
d) v + k
Solution:
Number of edges in ‘K’ components of ‘v’ vertices
= ∑ = 1 − 1
Where Vi is the number of vertices in ith component,
Since, ∑ = 1 =
So, ∑ = 1 − 1 = v – k
So, there are ‘v – k’ edges in a forest with ‘v’ vertices and ‘k’
components
2. If the strings of a language L can be effectively enumerated in
lexicographic (i.e., alphabetic) order, which of the following
statements is true?
a) L is necessarily finite
b) L is regular but not necessarily finite
c) L is context free but not necessarily regular
d) L is recursive but not necessarily context free

1

Solution:

To determine the membership of a string w in the language, let

|w| = n. We enumerate strings of length one, then two, then
Three.... then n if w L then it will be known when strings of

length n are enumerated. So the language is recursive as the

membership problem is decidable.
3. Let denote the transition function and ̂ denote the extended

transition function of the -NFA whose transition table is give

below:

a b

→ q0 {q2} {q1} {q0}

q1 {q2} {q2} {q3}
q2 {q0} ϕ ϕ

q3 ϕ ϕ {q2}
Then ̂ (q2, aba) is
a) ∅

b) {q0, q1, q3}

c) {q0, q1, q2}

d) {q0, q2, q3}

2

Solution:
State diagram:

̂ (q1, ) = (q1, q2, q0)
̂ (q2, ) = (q0, q2)
̂ (q3, ) = (q3)
̂ (q2, aba) = – closure (( ̂ q2, ab), a)
̂ (q2, a) = – closure (( ̂ q2, ), a)

= {q0, q1, q2}
̂ (q2, ab) = – closure (( ̂ q2, a), b))
= – closure ({q0, q1, q2}, b)
= – closure ({q0, b) ∪ (q1, b) ∪ (q2, b))
= – closure (q0, ∪ q3∪ a)
= {q0, q2} ∪{ q2} = {q0, q2, q3}

3

(q2, aba) = – closure (( ̂ q2, ab), a))
= (q0, q2, q3} a)
= – closure ({q0, a) ∪ (q2, a) ∪ (q3, a))
= – closure (q1, ∪ q2 ∪ )
= – closure (q1, ∪ q2)
= – closure (q1) ∪ – closure (q2)
= {q0, q1, q2} ∪ {q0, q2} = {q0, q1, q2}

4. Which of the following is/are un-decidable?
1. G is a CFG IS L(G) = Φ?
2. G is a CFG IS L(G) = Σ*?
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
Solution:
Case (1):
The emptiness problem of CFG is decidable
Case (2):
The completeness problem of CFG is undecidable.

4

Case (3):
This is a nontrivial problem so by Rice's theorem it is un-
decidable.
Case (4):
The NFA & DFA both accepts regular set.
So this is decidable.
5. Which of the following languages are context-free?

L1 = {ambnanbm|m, n ≥ 1}
L2 = {ambnanbm|m, n ≥ 1}|
L3 = {ambn|m = 2n + 1}
a) L1 and L2 only
b) L1 and L3 only
c) L2 and L3 only
d) L3 only
Solution:
L2 = {ambnanbm|m, n≥1}| is a CSL
This given L1
S → aSb
S → S1
S1 → b S1 |
L3 is a CFL

5

6. Consider the context-free grammar over the alphabet {a, b, c}
given below. S and T are non-terminals.
G1: S → aSb| T, T → cT
G2: S →bSa|T, T →cT
The language L(G1)∩ L(G2) is
a) Finite
b) Not finite but regular
c) Context-Free but not regular
d) Recursive but not context-free
Solution:
G1: S → aSb|T, T → cT
⟹ L (G1) = {am cn bm| m, n ≥ 0}
G2: S → bSa |T, T → cT
L (G2) = {bm cn am| m, n ≥ 0}
Both L (G1) ∩ L(G2) = c*
Regular but not finite

7. Which of the following conversions is not possible
(algorithmically)?
a) Regular grammar to context-free grammar
b) Non-deterministic FSA to deterministic FSA
c) Non-deterministic PDA to deterministic PDA
d) Non-deterministic Turing machine to deterministic Turing
machine.

6

Solution:
Case (a):
Any regular grammar is trivially a context free grammar. So this
statement is true'
Case (b):
By the construction of the subset machine every NFA can be
simulated by an equivalent DFA.
Case (c):
The language of all palindromes cannot be accepted by a NPDA'
So, the class of PDA are not of the same when the passes non-
Case (d):
Non-determinism does not add power to the TM, it is still the
R.E sets that are accepted
8. Which of the following conversion is not possible
(algorithmically)?
a) regular grammar to context-free grammar
b) nondeterministic FSA to deterministic FSA
c) nondeterministic PDA to deterministic PDA
d) nondeterministic TM to deterministic TM
9. Which one of the following statement is FALSE?
a) context-free languages are closed under union
b) context-free languages are closed under concatenation
c) context-free languages are closed under intersection

7

d) context-free languages are closed under Kleene closure
10. Which of the following regular expression identity is true?
a) r(*) = r*
b) (r*s*)* = (r + s)*
c) (r + s)* = r* + s*
d) r*s* = r* + s*
11. R1 and R2 are regular sets. Which of the following is not true?
a) R1 n R2 need not be regular
b) S* – R1 is regular
c) R1? R2 is regular
d) is regular
12. Recursive languages are
a) a proper superset of CFL
b) always recognized by PDA
c) are also called type 0 languages
d) always recognized by FSA
13. Which of the following problem is undecidable?
a) membership problem for CFL
b) membership problem for regular sets
c) membership problem for CSL
d) membership problem for type 0 languages

8

14. Recursively enumerable languages are not closed under

a) union
b) homomorphism
c) complementation
d) concatenation
15. Which of the following statement is wrong?
a) Any regular language can be generated by a context-free

grammar
b) Some non-regular languages cannot be generated by any

CFG
c) the intersection of a CFL and regular set is a CFL
d) All non-regular languages can be generated by CFGs.
16. Consider a language L for which there exists a Turing machine
™, T, that accepts every word in L and either rejects or loops for
every word that is not in L. The language L is
a) NP hard
b) NP complete
c) recursive
d) recursively enumerable

9

17. Which of the following strings is not generated by the following
grammar? S?
SaSbS|e
a) aabb
b) abab
c) aababb
d) aaabb

18. Which of the following is not primitive recursive but partially
recursive?
a) McCarthy’s function
b) Riemann function
c) Ackermann’s function
d) Bounded function

19. A language is represented by a regular expression (a)*(a + ba).
Which of the following string does not belong to the regular set
represented by the above expression?
a) aaa
b) aba
d) bbb

10

20. Which of the following regular expressions denotes a language
comprising of all possible strings over S = {a, b} of length n
where n is a multiple of 3.
a) (a + b + aa + bb + aba + bba)*
b) (aaa + bbb)*
c) ((a + b)(a + b)(a + b))*
d) (aaa + ab + a) + (bbb + bb + a)

21. A language L is accepted by a FSA if it is
a) CFL
b) CSL
c) recursive
d) regular

22. Which of the following denotes Chomskian hierarchy?
a) REG? CFL? CSL? type0
b) CFL? REG? type0? CSL
c) CSL? type0? REG? CFL
d) CSL? CFL? REG? type0

23. Let S = {a, b, c, d, e}. The number of strings in S* of length 4
such that no symbol is used more than once in a string is
a) 360
b) 120
c) 35

11

d) 36
24. Palindromes can’t be recognized by any FSA because
a) FSA cannot remember arbitrarily large amount of

information
b) FSA cannot deterministically fix the midpoint
c) Even if the mid-point is known an FSA cannot find whether

the second half of the string matches the first half
d) all of the above
25. The set of all strings over the alphabet S = {a, b} (including e) is
denoted by
a) (a + b)*
b) (a + b)+
c) a + b +
d) a*b*
26. baa*c denotes the set
a) {bnamcp|n, m, p = 1}
b) {banc|n = 0}
c) {banc|n = 1}
d) {w|w is a string of a, b, c}
27. (a + b)(cd)*(a + b) denotes the following set

a) {a(cd)nb|n = 1}

12

b) {a(cd)na|n = 1}? {b(cd)nb/n = 1}
c) {a(cd)na|n = 0}? {a(cd)nb/n = 0}? {b(cd)na/n = 0}?

{b(cd)nb/n = 0}
d) {acndnb|n = 1}
28. The concept of grammar is much used in this part of the
compiler
a) lexical analysis
b) parser
c) code generation
d) code optimization
29. The concept of FSA is much used in this part of the compiler
a) lexical analysis
b) parser
c) code generation
d) code optimization