# Multiple choice question for engineering

## Set 1

1. The context free languages are closed under:

a) Intersection

b) Complement

c) Kleene

d) None of the mentioned

### View Answer

2. Given Grammar G1:

S->aSb

S->e

Grammar G2:

R->cRd

R->e

If L(G)=L(G1) U L(G2), the number of productions the new starting variable would have:

a) 2

b) 3

c) 4

d) 1

### View Answer

3. Context free languages are not closed under:

a) Intersection

b) Intersection with Regular Language

c) Complement

d) All of the mentioned

### View Answer

4. Which of the following is incorrect?

There exists algorithms to decide if:

a) String w is in CFL L

b) CFL L is empty

c) CFL L is infinite

d) All of the mentioned

### View Answer

5. If the start symbol is one of those symbols which produce no terminal through any sequence, the CFL is said to be

a) nullable

b) empty

c) eliminated

d) none of the mentioned

### View Answer

6. Using the pumping constant n, If there is a string in the language of length between _____ and ____ then the language is infite else not.

a) n, 2n-1

b) 2n, n

c) n+1, 3n+6

d) 0, n+1

### View Answer

7. Which of the following is/are CFL not closed under?

a) Reverse

b) Homomorphism

c) Inverse Homomorphism

d) All of the mentioned

### View Answer

8. If L1 and L2 are context free languages, L1-L2 are context free:

a) always

b) sometimes

c) never

d) none of the mentioned

### View Answer

9. A___________ is context free grammar with atmost one non terminal in the right handside of the production.

a) linear grammar

b) linear bounded grammar

c) regular grammar

d) none of the mentioned

### View Answer

10. There is a linear grammar that generates a context free grammar

a) always

b) never

c) sometimes

d) none of the mentioned

### View Answer

## Set 2

1. The following format of grammatical notation is accepted by which of the following:

AB->CD

A->BC or

A->B or

A->a

where A, B, C, D are non terminal symbols and a is a terminal symbol.

a) Greibach Normal Form

b) Chomsky Nrmal Form

c) Kuroda Normal Form

d) None of the mentioned

### View Answer

2. Every Kuroda Normal form grammar generates ___________

a) Context free grammar

b) Context sensitive grammar

c) Unrestricted grammar

d) None of the mentioned

### View Answer

3. Which of the following can generate Unrestricted grammars?

a) Pentonnen Normal form

b) Floyd Normal form

c) Greibach Normal form

d) None of the mentioned

### View Answer

4. Given a grammar in GNF and a derivable string in the grammar with the length n, any ___________will halt at depth n.

a) top-down parser

b) bottom-up parser

c) multitape turing machine

d) none of the mentioned

### View Answer

5. Which of the following grammars is similar to Floyd Normal form?

a) Backus Naur Form

b) Kuroda Normal Form

c) Greibach Normal Form

d) Chomsky Normal Form

### View Answer

6. Which among the following can parse a context free grammar?

a) top down parser

b) bottom up parser

c) CYK algorithm

d) all of the mentioned

### View Answer

7. The standard version of CYK algorithm operates only on context free grammars in the following form:

a) Greibach Normal form

b) Chomsky Normal form

c) Backus Naur form

d) All of the mentioned

### View Answer

8. The __________ running time of CYK is O(n^{3} .|G|)

where n is the length of the parse string and |G| is the size of the context free grammar G.

a) worst

b) best

c) average

d) none of the mentioned

### View Answer

9. Which of the following is true for Valiants algorithm?

a) an extension of CYK

b) deals with efficient multiplication algorithms

c) matrices with 0-1 entries

d) all of the mentioned

### View Answer

10. Which among the following is a correct option in format for representing symbol and expression in Backus normal form?

a) <symbol> ->expression

b) <symbol>::=_expression_

c) <symbol>=<expression>

d) all of the mentioned

### View Answer

## Set 3

1. The format: A->aB refers to which of the following?

a) Chomsky Normal Form

b) Greibach Normal Form

c) Backus Naur Form

d) None of the mentioned

### View Answer

2. Which of the following does not have left recursions?

a) Chomsky Normal Form

b) Greibach Normal Form

c) Backus Naur Form

d) All of the mentioned

### View Answer

3. Every grammar in Chomsky Normal Form is:

a) regular

b) context sensitive

c) context free

d) all of the mentioned

### View Answer

4. Which of the production rule can be accepted by Chomsky grammar?

a) A->BC

b) A->a

c) S->e

d) All of the mentioned

### View Answer

5. Given grammar G:

(1)S->AS

(2)S->AAS

(3)A->SA

(4)A->aa

Which of the following productions denies the format of Chomsky Normal Form?

a) 2,4

b) 1,3

c) 1, 2, 3, 4

d) 2, 3, 4

### View Answer

6. Which of the following grammars are in Chomsky Normal Form:

a) S->AB|BC|CD, A->0, B->1, C->2, D->3

b) S->AB, S->BCA|0|1|2|3

c) S->ABa, A->aab, B->Ac

d) All of the mentioned

### View Answer

7. With reference to the process of conversion of a context free grammar to CNF, the number of variables to be introduced for the terminals are:

S->ABa

A->aab

B->Ac

a) 3

b) 4

c) 2

d) 5

### View Answer

8. In which of the following, does the CNF conversion find its use?

a) CYK Algorithm

b) Bottom up parsing

c) Preprocessing step in some algorithms

d) All of the mentioned

### View Answer

9. Let G be a grammar. When the production in G satisfy certain restrictions, then G is said to be in ___________.

a) restricted form

b) parsed form

c) normal form

d) all of the mentioned

### View Answer

10. Let G be a grammar: S->AB|e, A->a, B->b

Is the given grammar in CNF?

a) Yes

b) No

### View Answer

## Set 4

1. Which among the following is smallest for n=50

a) 2n2

b) n2+3n+7

c) n3

d) 2n

### View Answer

2. The space complexity of a turing machine is undefined if:

a) It is a multitape turing machine

b) If no string of length n causes T to use infinite number of tape squares

c) If some input of length n causes T to loop forever

d) None of the mentioned

### View Answer

3. In order to reduce the run time of a turing machine:

a) we can reduce the number of tapes

b) we can increase the number of tapes

c) use infinite tapes

d) none of the mentioned

### View Answer

4. Which of the following are basic complexity classes for a function f:N->N?

a) Ntime(f)

b) Nspace(f)

c) Space(f)

d) All of the mentioned

### View Answer

5. A function f is called __________ if there exists a TM T so that for any n and any input string of length n, T halts in exactly f(n) moves.

a) Step function

b) Step counting function

c) Inplace functions

d) None of the mentioned

### View Answer

6. Let f: N->N be a step counting function. Then for some constant C, Time(f) is a proper subset of Time(_______)

a) O(nf)

b) O(n+f)

c) O(n^{2}f^{2})

d) None of the mentioned

### View Answer

^{2}(f(n))

^{2}is the total number of moves required.

7. Which among the following is false?

If f=O(h) and g=O(k) for f,g,h,k:N->N, then

a) f+g = O(h+k)

b) fg = O(hk)

c) f^{g}=O(h^{k})

d) None of the mentioned

### View Answer

8. Which of the following is not correct for ZPP?

a) zero error probabalistic polynomial time

b) it runs in non-polynomial time

c) it returns an answer yes, no or do not know

d) none of the mentioned

### View Answer

9. ZPP is based on ________

a) Probabalistic turing machine

b) Alternative turing machine

c) Quantum turing machine

d) None of the mentioned

### View Answer

10. ZPP is exactly equal to the ____________of the classes RP and co-RP.

a) Union

b) Intersection

c) Concatenation

d) Difference

### View Answer

11. Suppose we have a las vegas algorithm C to prove ZPP is contained in RP and co-RP. Run C for double its expected running time.

By Markov’s inequality, the chance that it will answer before we stop is:

a) 1/2

b) 1/4

c) 1/3

d) none of the mentioned

### View Answer

12. State true or false:

Statement: ZPP is closed under complement function.

a) true

b) false

### View Answer

## Set 5

1. The most suitable data structure used to represent the derivations in compiler:

a) Queue

b) Linked List

c) Tree

d) Hash Tables

### View Answer

2. Which of the following statement is false in context of tree terminology?

a) Root with no children is called a leaf

b) A node can have three children

c) Root has no parent

d) Trees are collection of nodes, with a parent child relationship

### View Answer

3. In which order are the children of any node ordered?

a) From the left

b) From the right

c) Arbitrarily

d) None of the mentioned

### View Answer

4. Which among the following is the root of the parse tree?

a) Production P

b) Terminal T

c) Variable V

d) Starting Variable S

### View Answer

5. For the expression E*(E) where * and brackets are the operation, number of nodes in the respective parse tree are:

a) 6

b) 7

c) 5

d) 2

### View Answer

6. The number of leaves in a parse tree with expression E*(E) where * and () are operators

a) 5

b) 2

c) 4

d) 3

### View Answer

7. Which of the following does the given parse tree correspond to?

a) P->1100

b) P->0110

c) P->1100ε

d) P->0101

### View Answer

8. A grammar with more than one parse tree is called:

a) Unambiguous

b) Ambiguous

c) Regular

d) None of the mentioned

### View Answer

9. __________ is the acyclic graphical representation of a grammar.

a) Binary tree

b) Oct tree

c) Parse tree

d) None of the mentioned

### View Answer

10. Grammar is checked by which component of compiler

a) Scanner

b) Parser

c) Semantic Analyzer

d) None of the mentioned