# Multiple choice question for engineering

## Set 1

1. A CFG is ambiguous if

a) It has more than one rightmost derivations

b) It has more than one leftmost derivations

c) No parse tree can be generated for the CFG

d) None of the mentioned

### View Answer

2. Which of the following are always unambiguous?

a) Deterministic Context free grammars

b) Non-Deterministic Regular grammars

c) Context sensitive grammar

d) None of the mentioned

### View Answer

3. A CFG is not closed under

a) Dot operation

b) Union Operation

c) Concatenation

d) Iteration

### View Answer

4. Which of the following is an real-world programming language ambiguity?

a) dangling else problem

b) halting problem

c) maze problem

d) none of the mentioned

### View Answer

5. Which of the following is a parser for an ambiguous grammar?

a) GLR parser

b) Chart parser

c) All of the mentioned

d) None of the mentioned

### View Answer

6. A language that admits only ambiguous grammar:

a) Inherent Ambiguous language

b) Inherent Unambiguous language

c) Context free language

d) Context Sensitive language

### View Answer

7. Which of the following is an example of inherent ambiguous language?

a) {a^{n}|n>1}

b) {a^{n}b^{n}c^{m}d^{m}| n,m > 0}

c) {0^{n}1^{n}|n>0}

d) None of the mentioned

### View Answer

8. State true or false:

Statement: R->R|T T->ε is an ambiguous grammar

a) true

b) false

### View Answer

9. In context to ambiguity, the number of times the following programming statement can be interpreted as:

Statement: if R then if T then P else V

a) 2

b) 3

c) 4

d) 1

### View Answer

10. CFGs can be parsed in polynomial time using__________

a) LR parser

b) CYK algorithm

c) SLR parser

d) None of the mentioned

### View Answer

## Set 2

1. Given Language: {x | it is divisible by 3}

The total number of final states to be assumed in order to pass the number constituting {0, 1} is

a) 0

b) 1

c) 2

d) 3

### View Answer

2. A binary string is divisible by 4 if and only if it ends with:

a) 100

b) 1000

c) 1100

d) 0011

### View Answer

3. Let L be a language whose FA consist of 5 acceptance states and 11 non final states. It further consists of a dumping state. Predict the number of acceptance states in L^{c}.

a) 16

b) 11

c) 5

d) 6

### View Answer

^{c}, the FA can be obtained by exchanging the final and non-final states.

4. If L1 and L2 are regular languages, which among the following is an exception?

a) L1 U L2

b) L1 – L2

c) L1 ∩ L2

d) All of the mentioned

### View Answer

^{C}, L1 – L2 are regular language.

5. Predict the analogous operation for the given language:

A: {[p, q] | p ϵ A1, q does not belong to A2}

a) A1-A2

b) A2-A1

c) A1.A2

d) A1+A2

### View Answer

6. Which among the following NFA’s is correct corresponding to the given Language?

L= {xϵ {0, 1} | 3rd bit from right is 0}

a)

b)

c)

d) None of the mentioned

### View Answer

7. Statement 1: NFA computes the string along parallel paths.

Statement 2: An input can be accepted at more than one place in an NFA.

Which among the following options are most appropriate?

a) Statement 1 is true while 2 is not

b) Statement 1 is false while is not

c) Statement 1 and 2, both are true

d) Statement 1 and 2, both are false

### View Answer

8. Which of the following options is correct for the given statement?

Statement: If K is the number of states in NFA, the DFA simulating the same language would have states less than 2^{k}.

a) True

b) False

### View Answer

^{k}.

9. Let N (Q, ∑, δ, q0, A) be the NFA recognizing a language L. Then for a DFA (Q’, ∑, δ’, q0’, A’), which among the following is true?

a) Q’ = P(Q)

b) Δ’ = δ’ (R, a) = {q ϵ Q | q ϵ δ (r, a), for some r ϵ R}

c) Q’={q0}

d) All of the mentioned

### View Answer

10. There exists an initial state, 17 transition states, 7 final states and one dumping state, Predict the maximum number of states in its equivalent DFA?

a) 226

b) 224

c) 225

d) 223

### View Answer

^{k}.

## Set 3

1. To derive a string using the production rules of a given grammar, we use:

a) Scanning

b) Parsing

c) Derivation

d) All of the mentioned

### View Answer

2. Which of the following parser reaches the root symbol of the tree at last?

a) Top down parser

b) Bottom up parser

c) TOP down and Bottom up parser

d) None of the mentioned

### View Answer

3. Left corner parsing methof uses which of the following?

a) Top down parser

b) Bottom up parser

c) TOP down and Bottom up parser

d) None of the mentioned

### View Answer

4. Which of the following parser performs top down parsing?

a) LALR parser

b) LL parser

c) Recursive Accent parser

d) None of the mentioned

### View Answer

5. Which of the following is true for shift reduce parsers?

a) Scans and parses the input in one forward pass over the text, without any backup.

b) A shift command advances in the input stream by one symbol

c) LALR parser

d) All of the mentioned

### View Answer

6. State true or false:

Statement: LALR parsers uses tables rather than mutually recursive functions.

a) true

b) false

### View Answer

7. LALR in LALR parser stands for:

a) Left aligned left right parser

b) Look ahead left to right parser

c) Language Argument left to right parser

d) None of the mentioned

### View Answer

8. Which of the following can be a LALR parser generator?

a) YACC

b) GNU Bison

c) YACC and GNU Bison

d) None of the mentioned

### View Answer

9. Which of the following parsers do not relate to Bottom up parsing?

a) LL parser

b) Recursive descent parser

c) Earley parsers

d) All of the mentioned

### View Answer

10. Which of the following is true for a predictive parser?

a) Recursive Descent parser

b) no backtracking

c) Recursive Descent parser and no backtracking

d) None of the mentioned

### View Answer

## Set 4

1. Which kind of proof is used to prove the regularity of a language?

a) Proof by contradiction

b) Direct proof

c) Proof by induction

d) None of the mentioned

### View Answer

2. The language of balanced paranthesis is

a) regular

b) non regular

c) may be regular

d) none of the mentioned

### View Answer

3. State true or false:

Statement: Pumping lemma gives a necessary but not sufficient condition for a language to be regular.

a) true

b) false

### View Answer

4. Which of the following is/are an example of pigeon hole principle?

a) Softball team

b) Sock picking

c) Hair counting

d) All of the mentioned

### View Answer

5. Pigeonhole principle can be applied in the following computer science algorithms:

a) hashing algorithm

b) lossless compression algorithm

c) both (a) and (b)

d) none of the mentioned

### View Answer

6. If n objects are distributed over m places, and n < m, then some of the places receive:

a) at least 2 objects

b) at most 2 objects

c) no object

d) none of the mentioned

### View Answer

7. Which of the following fields may have pigeonhole principle violated?

a) Discrete mathematics

b) Computer Science

c) Quantum Mechanics

d) None of the mentioned

### View Answer

8. Which of the following is not an application of Pumping Lemma?

a) {0^{i}1^{i}|i>=0}

b) {0^{i}x|i>=0, x∈{0, 1}* and |x|<=i}

c) {0^{n}| n is prime}

d) None of the mentioned

### View Answer

9. Which of the following can refer a language to be non regular?

a) Pumping Lemma

b) Myphill Nerode

c) Both (a) and (b)

d) None of the mentioned

### View Answer

10. Which of the following is not an example of counting argument?

a) Pigeonhole principle

b) Dirichlet’s drawer principle

c) Dirichlet’s box principle

d) None of the mentioned

### View Answer

## Set 5

1. Which of the given problems are NP-complete?

a) Node cover problems

b) Directed Hamilton Circuit Problem

c) Both (a) and (b)

d) None of the mentioned

### View Answer

2. Which of the following problems do not belong to Karp’s 21 NP-complete problems?

a) Vertex Cover problems

b) Knapsack

c) 0-1 integer programming

d) None of the mentioned

### View Answer

3. Which of the following problems were reduced to Knapsack?

a) Exact Cover

b) Max Cut

c) 0-1 integer programming

d) None of the mentioned

### View Answer

4. An exact cover problem can be represented using:

a) incidence matrix

b) bipartite graph

c) both (a) and (b)

d) none of the mentioned

### View Answer

5. For which of the following, greedy algorithm finds a minimal vertex cover in polynomial time?

a) tree graphs

b) bipartite graphs

c) both (a) and (b)

d) none of the mentioned

### View Answer

6. Hamilton circuit problem can have the following version/s as per the input graph:

a) directed

b) undirected

c) both (a) and (b)

d) none of the mentioned

### View Answer

7. Hamilton Circuit problem is a special case of ____________

a) travelling salesman problem

b) halting problem

c) hitting set

d) none of the mentioned

### View Answer

8. Which of the following cannot solve Hamilton Circuit problem?

a) DNA Computer

b) Monte Carlo algorithm

c) Dynamic programming

d) None of the mentioned

### View Answer

9. State true or false:

Statement: Hamiltonian cycles through any fixed edge is always even, so if one such cycle is given, the second one must also exists.

a) true

b) false

### View Answer

10. Fibonacci number falls in the category of _________ combinatorics.

a) Algebric

b) Enumerative

c) Analytic

d) Extremal