# Multiple choice question for engineering

## Set 1

1. A language L from a grammar G = { VN, Σ, P, S} is

a) Set of symbols over VN

b) Set of symbols over Σ

c) Set of symbols over P

d) Set of symbols over S

### View Answer

2. The transitional function of a DFA is

a) Q X Σ→Q

b) Q X Σ→2Q

c) Q X Σ→2n

d) Q X Σ→Qn

### View Answer

3. The transitional function of a NFA is

a) Q X Σ→Q

b) Q X Σ→2Q

c) Q X Σ→2n

d) Q X Σ→Qn

### View Answer

4) Maximum number of states of a DFA converted from a NFA with nstates is

a) n

b) n2

c) 2n

d) None of these

### View Answer

5. Basic limitations of finite state machine is

a) It cannot remember arbitrarily large amount of information

b) In cannot remember state transitions

c) In cannot remember grammar for a language

d) It cannot remember language generated from a grammar

### View Answer

6. The string WWR is not recognized by any FSM because

a) A FSM cannot remember arbitrarily large amount of information

b) A FSM cannot fix the midpoint

c) A FSM cannot match W with WR

d) A FSM cannot remember first and last inputs

### View Answer

7. A finite automata recognizes

a) Any Language

b) Context Sensitive Language

c) Context Free Language

d) Regular Language

### View Answer

## Set 2

1. Which is true for Dead State?

a) It cannot be reached anytime

b) There is no necessity of the state

c) If control enters no way to come out from the state

d) If control enters FA deads

### View Answer

2. Which is true for Moore Machine?

a) Output depends on present state

b) Output depends on present input

c) Output depends on present state and present input

d) Output depends on present state and past input

### View Answer

3. Which is true for Mealy Machine?

a) Output depends on present state

b) Output depends on present input

c) Output depends on present state and present input

d) Output depends on present state and past input

### View Answer

4. Which is true for in accessible state?

a) It cannot be reached anytime

b) There is no necessity of the state

c) If control enters no way to come out from the state

d) If control enters FA deads

### View Answer

5. In Mealy Machine O/P is associated with

a) Present state

b) Next state

c) Input

d) None of the mentioned

### View Answer

6. In Moore Machine O/P is associated with

a) Present state

b) Next state

c) Input

d) None of the mentioned

### View Answer

7. Which type string is accepted by the following finite automata?

a) All string

b) Null string

c) No string

d) None of the mentioned

### View Answer

8. Myhill-Nerode Theorem is used for __________

a) Minimization of DFA

b) Maximization of NFA

c) Conversion of NFA

d) Conversion of DFA

### View Answer

## Set 3

1. Number of states of FSM required to simulate behaviour of a computer with a memory capable of storing “m” words, each of length ‘n’

a) m x 2^{n}

b) 2^{mn}

c) 2^{(m+n)}

d) All of the mentioned

### View Answer

^{mn}.

2. An FSM with

a) M can be transformed to Numeral relabeling its states

b) M can be transformed to N, merely relabeling its edges

c) Both of the mentioned

d) None of the mentioned

### View Answer

3. Which of the following is right?

a) A Context free language can be accepted by a deterministic PDA

b) union of 2 CFLs is context free

c) The intersection of two CFLs is context free

d) The complement of CFLs is context free

### View Answer

4. Consider the following two statements:

S1: { 0^{2n} |n >= l} is a regu1ar language

S2: { 0^{m} 0^{n} 0^{(m+n)} l m >= 1 and n >= 2} is a regu1ar language

Which of the following is true?

a) Only S1 is correct

b) Only S2 is correct

c) Both S1 and S2 are correct

d) None of S1 and S2 is correct

### View Answer

^{n}where n >= 1. And S2 can be written as (00)

^{ (m+n)}where m >=2 and n >= 1. S2 can be further reduced to (00)

^{x}where x >= 3. SO we can write regular grammars for both G1 -> G100/00 (For S1) G2 -> G200/000000 (For S2).

5. Which of the following pairs of regular expressions are equivalent?

a) 1(01)* and (10)*1

b) x (xx)* and (xx)*x

c) x^{+} and x^{+} x^{(*+)}

d) All of the mentioned

### View Answer

6. Given a NFA with N states, the maximum number of states in an equivalent minimized DFA is at least.

(a) N^{2}

(b) 2^{N}

(c) 2N

(d) N!

### View Answer

7. Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?

(a) L = O

(b) L is regular but not O

(c) L is context free but not regular

(d) L is not context free

### View Answer

8. Which of the following are not regular?

a) String of )’s which has length that is a perfect square

b) Palindromes Consisting of 0’s 1’s

c) String of 0’s whose length is a prime number

d) All of the mentioned

### View Answer

9. If ∑ = {a, b, c, d, e, f} then number of strings in ∑ of length 4 such that no symbol is used more than once in a string is

a) 35

b) 360

c) 49

d) 720

### View Answer

10. 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

d) Context-free languages are closed under Kleene closure

### View Answer

## Set 4

1. If A ∩ B = B, then

a) A ⊂ B

b) A = ø

c) B ⊂ A

d) B = ø

### View Answer

2. Empty set is a

a) Invalid set

b) Infinite set

c) Finite set

d) None of the mentioned

### View Answer

3. If A, B and C are any three sets, then A – (B ∪ C) is equal to

a) (A – B) ∪ (A – C)

b) (A – B) ∪ C

c) (A – B) ∩ (A – C)

d) (A – B) ∩ C

### View Answer

4. A = {x: x ≠ x }represents

a) {0].

b) {1}

c) {}

d) {x}

### View Answer

5. If A, B, C be three sets such that A ∪ B = A ∪ C and A ∩ B = A ∩ C, then

a) A=B

b) A=C

c) B=C

d) A=B=C

### View Answer

6. The number of proper subsets of the set {1, 2, and 3} is.

a) 8

b) 6

c) 7

d) 5

### View Answer

7. If A and B are any two sets, then A ∪ (A ∩ B) is equal to

a) A

b) B

c) A^C

d) B^C

### View Answer

8. If A, B and C are any three sets, then A × (B ∪ C) is equal to.

a) (A × B) ∪ (A × C)

b) (A × B) ∩ (A × C)

c) (A ∪ B) × (A ∪ C)

d) None of the mentioned

### View Answer

## Set 5

1. DAG representation of a basic block allows

a) Automatic detection of local common sub expressions

b) Detection of induction variables

c) Automatic detection of loop variant

d) None of the mentioned

### View Answer

2. Inherited attribute is a natural choice in

a) Tracking declaration of a variable

b) Correct use of L and R values

c) All of the mentioned

d) None of the mentioned

### View Answer

3. An intermediate code form is

a) Postfix notation

b) Syntax Trees

c) Three Address code

d) All of the mentioned

### View Answer

4. Which of the following actions an operator precedence parser may take to recover from an error?

a) Insert symbols onto the stack

b) Delete symbols from the stack

c) Inserting or deleting symbols from the input

d) All of the mentioned

### View Answer

5. The output of lexical analyzer is

a) A set of regular expression

b) Syntax tress

c) Set of Token

d) String of Characters

### View Answer

6. Which of the following is used for grouping of characters into tokens?

a) Parser

b) Code optimization

c) Code generator

d) Lexical analyser

### View Answer

7. Shift reduce parsers are

a) Top down parser

b) Bottom up parser

c) Maybe both

d) None of the mentioned

### View Answer

8. A bottom up parser generates

a) Right most derivation

b) Right most derivation in reverse

c) Left most derivation

d) Left most derivation in reverse

### View Answer

9. A garbage is

a) Unallocated storage

b) Allocated storage whose access paths are destroyed?

c) Allocated storage

d) Uninitialized storage

### View Answer

10. A optimizing compiler

a) Is optimized to occupy less space

b) Is optimized to take less time for execution

c) Optimized the code

d) None of the mentioned