# Compiler Design & TOC Test - 3 - PDF Flipbook

Compiler Design & TOC Test - 3

219 Views

5 Downloads

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

Answer: (c)

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

Answer: (d)

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}

Answer: (c)

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

Answer: (d)

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

Answer: (b)

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

Answer: (b)

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.

Answer: (c)

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-

deterministic is added.

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

Answer: (c)

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

Answer: (c)

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*

Answer: (b)

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

Answer: (a)

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

Answer: (a)

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

Answer: (d)

14. Recursively enumerable languages are not closed under

a) union

b) homomorphism

c) complementation

d) concatenation

Answer: (c)

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.

Answer: (d)

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

Answer: (d)

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

Answer: (d)

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

Answer: (c)

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

c) ababad. Aa

d) bbb

Answer: (c)

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)

Answer: (c)

21. A language L is accepted by a FSA if it is

a) CFL

b) CSL

c) recursive

d) regular

Answer: (d)

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

Answer: (a)

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

Answer: (b)

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

Answer: (d)

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*

Answer: (a)

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}

Answer: (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}

Answer: (c)

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

Answer: (b)

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

Answer: (a)

30. Can a DFSA simulate a NFSA

a) No

b) Yes

c) Sometimes

d) depends on NFA

Answer: (b)

13

Data Loading...