Select Page
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages
Filter by Categories
nmims post
Objective Type Set
Online MCQ Assignment
Question Solution
Solved Question
Uncategorized

# 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

Answer: b [Reason:] The definition of the grammar is set of symbols over Σ.

2. The transitional function of a DFA is
a) Q X Σ→Q
b) Q X Σ→2Q
c) Q X Σ→2n
d) Q X Σ→Qn

Answer: a [Reason:] Q is the finite set and let be a finite set of symbols so Q X Σ fives no of states.

3. The transitional function of a NFA is
a) Q X Σ→Q
b) Q X Σ→2Q
c) Q X Σ→2n
d) Q X Σ→Qn

Answer: b [Reason:] Let Q be a finite set and let be a finite set of symbols. Also let be a function from Q to 2Q.All the elements of Q a state, the transition function, q0 the initial state and A the set of accepting states. Then a nondeterministic finite automaton is a 5-tuple < Q , , q0 , , A > .

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

Answer: c [Reason:] Take the NFA with states {qo,q1}, alphabet Σ={a}, initial state q0, transitions δ(q0,a)=q0, δ(q0,a)=q1 and final state q1. It generates the same language as the DFA with the same set of states and alphabet, but transitions δ(q0,a)=q1 and δ(q1,a)=q1.

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

Answer: b [Reason:] Because it does to store its previous state of the transition.

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

Answer: b [Reason:] Palindromes cannot be recognised by FSM.

7. A finite automata recognizes
a) Any Language
b) Context Sensitive Language
c) Context Free Language
d) Regular Language

Answer: d [Reason:] All regular languages are implemented by the finite automata.

## 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

Answer: c [Reason:] It is a rejecting state for if the control enters it reaches the dead end and cannot reach an accepting state.

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

Answer: a [Reason:] The definition states that moore machines output is determined by the current state only.

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

Answer: c [Reason:] The definition states that its output is determined by current state and current input.

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

Answer: a [Reason:] The very meaning of in accessible state is that it cannot be reached at any point of time.

5. In Mealy Machine O/P is associated with
a) Present state
b) Next state
c) Input
d) None of the mentioned

Answer: b [Reason:] The definition states that its output is determined by current state and current input.

6. In Moore Machine O/P is associated with
a) Present state
b) Next state
c) Input
d) None of the mentioned

Answer: a [Reason:] The definition states that moore machines output is determined by the current state only.

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

Answer: b [Reason:] Null strings are not accepted by finite automata.

8. Myhill-Nerode Theorem is used for __________
a) Minimization of DFA
b) Maximization of NFA
c) Conversion of NFA
d) Conversion of DFA

Answer: a [Reason:] Myhill–Nerode theorem provides a necessary and sufficient condition for a language to be regular. The Myhill–Nerode theorem can be generalized to trees. And used for minimization of DFA.

## 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 2n
b) 2mn
c) 2(m+n)
d) All of the mentioned

Answer: b [Reason:] For every Data here length is n and memory’s state is defined in terms of power of 2, Here the total memory capability for all the words = mn Hence the number of states is2mn.

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

Answer: c [Reason:] The Definition of FSM states that M can be transformed to N by relabeling its states or its edges.

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

Answer: b [Reason:] Context-free languages are closed under the following operations. The Kleene star, the concatenation, the union and the intersection.

4. Consider the following two statements:
S1: { 02n |n >= l} is a regu1ar language
S2: { 0m 0n 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

Answer: c [Reason:] S1 can be written as (00)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

Answer: d [Reason:] Rule (pq)*p=p (qp)* Therefore–(xx*) (x*x**) (xx*)(x*x*) [Using x**=x] (xx*)(x*) [Using x*x*=x*] (xx*) [Using x*xx*=x*) x+

6. Given a NFA with N states, the maximum number of states in an equivalent minimized DFA is at least.
(a) N2
(b) 2N
(c) 2N
(d) N!

Answer: b [Reason:] The initial state of the DFA constructed from this NFA is the set of all NFA states that are reachable from state 1 by ε-moves; that is, it is the set {1, 2, and 3}. A transition from states1, 2, and 3 by input symbol 0 must follow either the arrow from state 1 to 2, or from state 3 to 4. Also, neither state 2 nor 4 have outgoing ε-moves.

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

Answer: b [Reason:] The grammar itself is not regular but language L is regular as L can be represented using a regular grammar, for example S -> S00/00.

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

Answer: d [Reason:] Strings of odd number of zeroes can be generated by the regular expression (00) *0.Pumping lemma can be used to prove the non-regularity of the other options.

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

Answer: b [Reason:] Here string length is 4 so we create string of length 4 by 6 values firstly we arrange any value by 6 methods. Then Remaining numbers are 5 so we can arrange them by 5 methods then remaining numbers are 4 so we arrange them by 4 methods and then 3.Thus 6*5*4*3=360.

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

Answer: c [Reason:] CFL is closed under Kleene closure, concatenation, and Union

## Set 4

1. If A ∩ B = B, then
a) A ⊂ B
b) A = ø
c) B ⊂ A
d) B = ø

Answer: c [Reason:] Since A ∩ B = B , hence B ⊂ A .

2. Empty set is a
a) Invalid set
b) Infinite set
c) Finite set
d) None of the mentioned

Answer: c [Reason:] Empty set is a finite set.

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

Answer: c [Reason:] it is De’ Morgan law.

4. A = {x: x ≠ x }represents
a) {0].
b) {1}
c) {}
d) {x}

Answer: c [Reason:] That is a fact.

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

6. The number of proper subsets of the set {1, 2, and 3} is.
a) 8
b) 6
c) 7
d) 5

Answer: b [Reason:] Number of proper subsets of the set {1, 2, 3) = 2³ – 2 = 6.

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

Answer: a [Reason:] A ∩ B ⊆ A Hence A ∪ (A ∩ B) = A.

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

Answer: a [Reason:] It is distributive law.

## 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

Answer: a [Reason:] it detects local sub expression .

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

Answer: a [Reason:] These attribute keep a check on variable declaration

3. An intermediate code form is
a) Postfix notation
b) Syntax Trees
d) All of the mentioned

Answer: d [Reason:] Intermediate code generator receives input from its predecessor phase, semantic analyzer, in the form of an annotated syntax tree.

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

Answer: d [Reason:] All these symbols are used to recover operator precedence parser from an error

5. The output of lexical analyzer is
a) A set of regular expression
b) Syntax tress
c) Set of Token
d) String of Characters

Answer: c [Reason:] lexical analysis is the process of converting a sequence of characters into a sequence of tokens

6. Which of the following is used for grouping of characters into tokens?
a) Parser
b) Code optimization
c) Code generator
d) Lexical analyser

Answer: d [Reason:] lexical analysis is the process of converting a sequence of characters into a sequence of tokens.

7. Shift reduce parsers are
a) Top down parser
b) Bottom up parser
c) Maybe both
d) None of the mentioned

Answer: b [Reason:] This corresponds to starting at the leaves of the parse tree. It can be thought of. A process of reducing the string in question to the start symbol of the grammar. Bottom-up parsing is also known as shift-reduce parsing.

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

Answer: b [Reason:] This corresponds to starting at the leaves of the parse tree. It can be thought of. a process of reducing the string in question to the start symbol of the grammar. Bottom-up parsing is also known as shift-reduce parsing.

9. A garbage is
a) Unallocated storage
b) Allocated storage whose access paths are destroyed?
c) Allocated storage
d) Uninitialized storage

Answer: b [Reason:] these are more like memory loacations with values whose pointers have been revoked

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