Multiple choice question for engineering
Set 1
1. The classes of languages P and NP are closed under certain operations, and not closed under others. Decide whether P and NP are closed under each of the following operations.
1. Union
2. Intersection
3. Intersection with a regular language
4. Kleene closure (star)
5. Homomorphism
6. Inverse homomorphism
a) P is not closed under union
b) NP is not closed under intersection.
c) None of the mentioned
d) Both of the mentioned
Answer
Answer: d [Reason:] Both P and NP are closed under each of these operations.
2. Ndfa and dfa accept same languages
a) True
b) False
Answer
Answer: a [Reason:] They both are equivalent.
3. __________ a part of a compiler that is responsible for recognizing syntax.
a) Parser
b) Bzr
c) Linker
d) Optimizer
Answer
Answer: a [Reason:] Parser recognises all the syntax of the language.
4. __________ a part of a compiler that takes as input a stream of characters and produces as output a stream of words along with their associated syntactic categories.
a) Parser
b) Optimizer
c) Scanner
d) None of the mentioned
Answer
Answer: c [Reason:] A compiler’s scanner reads an input stream that consists of characters and produces an output stream that contains words, each labelled with its Syntactic category.
5. _________an IR-to-IR transformer that tries to improve the IR program in some way.
a) Optimizer
b) Parser
c) All of the mentioned
d) None of the mentioned
Answer
Answer: a [Reason:] The optimizer is an IR-to-IR transformer that tries to improve the IR program in some way.
6. _________a phase of a compiler that maps the IR program into the instruction set and the finite resources of the target machine.
a) Optimizer
b) Parser
c) Optimizer & Parser
d) None of the mentioned
Answer
Answer: d [Reason:] In a two-phase compiler, ensures that there is a source program and an object program.
7. If the NFA N has n states, then the corresponding DFA D has 2n states
a) True
b) False
Answer
Answer: a [Reason:] nfa has n then dfa has at max 2^n.
8. An NFA is nothing more than a ε-NFA with no ε transitions
a) True
b) False
Answer
Answer: a [Reason:] An NFA is nothing more than a ε-NFA with no ε transitions. Thus • δ (q, ε) for all states q = ∅.
9. For every DFA, there is a ε-NFA that accepts the same language
a) True
b) False
Answer
Answer: a [Reason:] For every DFA, there is a ε-NFA that accepts the same language and Vice Versa.
10. DFAs, NFAs, and ε-NFA s are equivalent
a) True
b) False
Answer
Answer: a [Reason:] for every NFA there is a ε-NFA that accepts the similar language, and vice versa.
Set 2
1. Conversion of a DFA to an NFA
a) Is impossible
b) Requires the subset construction
c) Is Chancy
d) Is nondeterministic
Answer
Answer: b [Reason:] In order to convert NDFA to DFA we work with sets of state where each state in the DFA corresponds to a set of NFA states.
2. A regular language corresponds to
a) An alphabet
b) Set of strings over an alphabet
c) A DFA only
d) A DFA or an NFA
Answer
Answer: b [Reason:] A regular grammar takes in all strings over an alphabet.
3. An NFA may be converted to a DFA using
a) Induction
b) A construction
c) Contradiction
d) Compilation
Answer
Answer: b [Reason:] subset construction is used to convert a NFA into DFA.
4. The subset construction shows that every NFA accepts a
a) String
b) Function
c) Regular language
d) Context-free language
Answer
Answer: c [Reason:] Like DFAs, NFAs only recognize regular languages.
5. Construct a NDFA for the following regular expression
(a∪b)*aba(a∪b)*
a) 
b) 
c) 
d) None of the mentioned
Answer
Answer: a [Reason:] The NDFA initially takes either a or b followed by a then b then reaches the final state or takes iterations of a or b to reach the final state.
6. Which is the application of NFA
a) A regular language is produced by union of two regular languages
b) The concatenation of two regular languages is regular
c) The Kleene closure of a regular language is regular
d) All of the mentioned
Answer
Answer: d [Reason:] As per its definition.
7. For every NFA a deterministic finite automaton (DFA) can be found that accepts the same language.
a) True
b) False
Answer
Answer: a [Reason:] Therefore it is possible to convert an existing NFA into a DFA for the purpose of implementing a simpler machine. Which is executed by using the powerset construction.
8. Like DFAs, NFAs only recognize regular languages
a) True
b) False
Answer
Answer: a [Reason:] It is a known fact.
Set 3
1. Which of the following is the fastest logic ?
a) TTL
b) ECL
c) CMOS
d) LSI
Answer
Answer: b [Reason:] In electronics, emitter-coupled logic (ECL) is a high-speed integrated circuit.
2. A bottom up parser generates
a) Right most derivation
b) Rightmost derivation in reverse
c) Leftmost derivation
d) Leftmost derivation in reverse
Answer
Answer: b [Reason:] This corresponds to starting at the leaves of the parse tree also known as shift-reduce parsing.
3. A grammar that produces more than one parse tree for some sentence is called
a) Ambiguous
b) Unambiguous
c) Regular
d) None of the mentioned
Answer
Answer: a [Reason:] ambiguous grammar has more than one parse tree.
4. An optimizer Compiler
a) Is optimized to occupy less space
b) Both of the mentioned
c) Optimize the code
d) None of the mentioned
Answer
Answer: d [Reason:] In computing, an optimizing compiler is a compiler that tries to minimize or maximize some attributes of an executable computer program.
5. The linker
a) Is similar to interpreter
b) Uses source code as its input
c) I s required to create a load module
d) None of the mentioned
Answer
Answer: c [Reason:] It is a program that takes one or more object files generated by a compiler and combines them into a single executable file, library file, or another object file.
6. A latch is constructed using two cross coupled
a) AND OR gates
b) AND gates
c) NAND and NOR gates
d) NAND gates
Answer
Answer: d [Reason:] It has two inputs and one output.
7. Pee Hole optimization
a) Loop Optimization
b) Local Optimization
c) Constant folding
d) Data Flow analysis
Answer
Answer: c [Reason:] More loops are added.
8. The optimization which avoids test at every iteration is
a) Loop unrolling
b) Loop jamming
c) Constant folding
d) None of the mentioned
Answer
Answer: a [Reason:] Execution speed is enhanced by sacrificing bits.
9. Scissoring enables
a) A part of data to be displayed
b) Entire data to be displayed
c) None of the mentioned
d) No data to be displayed
Answer
Answer: a [Reason:] Displays only some part of the data.
10. Shift reduce parsers are
a) Top down Parser
b) Bottom Up parser
c) May be top down or bottom up
d) None of the mentioned
Answer
Answer: b [Reason:] Also known as shift reduce parser.
Set 4
1. Given an arbitrary non-deterministic finite automaton (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
Answer: b [Reason:] if the NFA has n states, the resulting DFA may have up to 2n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs.
2. What can be said about a regular language L over {a} whose minimal finite state automaton has two states?
a) L must be {an| n is odd}
b) L must be {an| n is even}
c) L must be {an| n is even}
d) Either L must be {an | n is odd}, or L must be {an | n is even}
Answer
Answer: d [Reason:] There are two states. When first state is final, it accepts even no. of a’s. When second state is final, it accepts odd no. of a’s.
3. How many minimum states are required to find whether a string has odd number of 0’s or not?
a) 1
b) 2
c) 3
d) 4
Answer
Answer: b [Reason:] 2
4. The number of states in DFA that accepts the language L(M) ∩ L(N) is ________
a) 0
b) 1
c) 2
d) 3
Answer
Answer: B [Reason:] In DFA M: all strings must end with ‘a’. In DFA N: all strings must end with ‘b’. So the intersection is empty. For an empty language, only one state is needed.
5. Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X0, X1 and X0.How are X1 and X2 are related ?
X0 = 1 X1
X1 = 0 X1 + 1 X2
X2 = 0 X1 + {λ}
Which one of the following represents the strings in X0?
a) 10 (0* + (10)*)1
b) 10 (0* + (10)*)*1
c) 10 (0* + (10)*)*1
d) 10 (0 + 10)*1 + 110 (0 + 10)*1
Answer
Answer: c [Reason:] The smallest possible string by given grammar is “11”.
X0 = 1X1
= 11X2 [Replacing X1 with 1X2]
= 11 [Replacing X2 with λ]
The string “11” is only possible with option (C).
6. Which of the following languages is/are regular?
L1: {wxwR ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} wR is the reverse of string w
L2: {anbm ⎪m ≠ n and m, n≥0
L3: {apbqcr ⎪ p, q, r ≥ 0}
a) L1 and L3 only
b) L2
c) L2 and L3 only
d) L3 only
Answer
Answer: a [Reason:] L3 is simple to guess, it is regular.
7. The reorganizing capability of NDFA and DFA
a) May be diffent
b) Must be different
c) Must be same
d) None of the mentioned
Answer
Answer: c [Reason:] Given any NDFA one can construct an equivalent DFA.
8. Which of the following is not regular?
a) String whose length is perfect square and consists of 0s
b) Palindromes consisting of 0’s and 1’s
c) Both of the mentioned
d) None of the mentioned
Answer
Answer: c [Reason:] Strings of odd numbers of zeros can be generated by regular expression (00)*0.
9. Which of the following pairs of regular expression are equivalent?
a) 1(01)* and (10)*1
b) X(xx)* and (xx)*x
c) None of the mentioned
d) Both of the mentioned
Answer
Answer: D [Reason:] R1 and R2 are reverse of each other. If ant one of them can be generated them the other can be generated as well.
Set 5
1. In C programming language, which of the following type of operators have the highest precedence
a) Relational Operators
b) Equality Operators
c) Logical Operators
d) Arithmetic Operators
Answer
Answer: d [Reason:] No other operator has higher precedence than arithmetic operator
2. Which of the following operators has the highest precedence?
a) Unary +
b) *
c) >=
d) ==
Answer
Answer: a [Reason:] unary operators have max precedence in over all other arithmetic operators
3. If i=1 j=2,k=3, then what is the value of the expression
!((j + k) > (i + 5))
a) 6
b) 5
c) 1
d) 0
Answer
Answer: c [Reason:] !((2+3)>(1+5))
!(5>6)
Since the condition is false hence !(0)
And complement of 0 is 1.
4. The expression 5 – 2 – 3 * 5 – 2 will evaluate to 18, if – is left associative and
a) * has precedence over *
b) * has precedence over –
c) – has precedence over *
d) – has precedence over –
Answer
Answer: c [Reason:] if – has precedence over* and if it associates from the right
5. Coercion
a) Takes place over an assignment operator
b) Operator has operands of various types
c) None of the mentioned
d) Both of the mentioned
Answer
Answer: d [Reason:] conversion between compatible types
6. Choose the correct statement
a) Expressions evaluated at compile time
b) String constants concatenated at compile time
c) None of the mentioned
d) Both of the mentioned
Answer
Answer: d [Reason:] The statements are true
7. Which of the following operators takes only integer operands ?
a) +
b) *
c) /
d) %
Answer
Answer: d [Reason:] Two integers are taken to be input
8. Pick the operators that associate from the left
a) +
b) ,
c) <
d) All of the mentioned
Answer
Answer: d [Reason:] They are left associative
9. Pick the operators that associate from the right
a) ?:
b) +=
c) =
d) All of the mentioned
Answer
Answer: d [Reason:] They are right associative
10. Pick the operators that associate from left to right
a) &&
b) ?:
c) ,
d) All of the mentioned
Answer
Answer: d [Reason:] They left to right associative
Total Views: 12
