Multiple choice question for engineering
Set 1
1. Can a DFA simulate NDFA
a) No
b) Yes
c) Sometimes
d) Depends on NDFA
Answer
Answer: b [Reason:] Yes it can be done through power set construction.
2. Find the wrong statement?
a) The language accepted by finite automata are the languages denoted by regular expression
b) Every DFA has a regular expression denoting its language
c) For a regular expression r, there does not exists NDFA with L® ant transit that accept
d) None of the mentioned
Answer
Answer: c [Reason:] The vice versa is true.
3. Regular expression a/b denotes the set
a) {a}
b) {€,a,b}
c) {a,b}
d) {ab}
Answer
Answer: c [Reason:] Either a is the output or b hence it’s {a, b}.
4. The behaviour of a NFA can be stimulated by DFA
a) Always
b) Sometimes
c) Never
d) Depends on NFA
Answer
Answer: a [Reason:] It can be done through power set construction.
5. For any DFA state {qi,qj…qm} If some qj is a final state in the NFA Then {qi,qj…qm}, is a final state in the DFA.True or False
a) True
b) False
Answer
Answer: a [Reason:] It the the standard procedure to convert NFA to DFA.
6. The relation between NFA-accepted languages and DFA accepted languages is
a) >
b) <
c) =
d) <=
Answer
Answer: c [Reason:] The no of languages accepted by NFA and DFA is equal.
7. In regular expressions, the operator ‘*’ stands for
a) Concatenation
b) Selection
c) Iteration
d) Addition
Answer
Answer: c [Reason:] It indicates iterations which can vary from zero to any number.
Set 2
1. A deterministic finite automation (DFA)D with alphabet ∑= {a,b} is given below
Which of the following is a valid minimal DFA which accepts the same language as D?
a) 
b) 
c) 
d)
Answer
Answer: a [Reason:] Options (B) and (C) are invalid because they both accept ‘b’ as a string which is not accepted by give DFA. D is invalid because it accepts bb+a which are not accepted by given DFA.
2. The lexical analysis for a modern language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?
a) Finite state automata
b) Deterministic pushdown automata
c) Non-deterministic pushdown automata
d) Turing machine
Answer
Answer: a [Reason:] Initially in lexical analysis the program is divided into tokens. Tokens can be expressed as regular expressions: [a-zA-Z] [a-zA-Z0-9]*
the keyword if is given by if.
Integers are given by [+-]? [0-9]+.
3. Is empty string a valid input in Ndfa
a) True
b) False
Answer
Answer: a [Reason:] Empty strings can be inputted n a NDFA.
4. What is the complement of the language accepted by the NFA shown below? Assume ∑ = {a} and ε is the empty string
a) Φ
b) ε
c) a
d) {a, ε}
Answer
Answer: b [Reason:] The given alphabet ∑ contains only one symbol {a} and the given NFA accepts all strings with any number of occurrences of ‘a’. Hence the complement is an empty string.
5. Given the language L = {ab, aa, baa}, whih of the following strings are in L*?
1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa
a) 1, 2 and 3
b) 2, 3 and 4
c) 1, 2 and 4
d) 1, 3 and 4
Answer
Answer: c [Reason:] Any combination of strings in set {ab, aa, baa} will be in L*.
“abaabaaabaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “ab aa baa ab aa”
2) “aaaabaaaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “aa ab aa aa”
3) “baaaaabaaaab” cannot be partitioned as a combination of strings in set {ab, aa, baa}
4) “baaaaabaa” can be partitioned as a combination of strings in set {ab, aa, baa}. The partitions are “baa aa ab aa”.
6. Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. Complete the partially completed DFA that accepts this language is shown below.
The missing arcs in the DFA are
a) 
b) 
c) 
d) 
Answer
Answer: d [Reason:] State ‘q’ is trap state. All other states are accepting states. In state 00, DFA must move to ‘q’ for input symbol 0. All (non-trap) states indicate names indicate the characters seen before reaching that particular state. Option (D) is the only options that follow these rules.
7. Which of the following problems occur?
1) Does a given program ever produce an output?
2) If L is a CFL, then is L’ is also context-free?
3)L’ is regular only if L is regular?
4) If L is a recursive language, then, L’ is also recursive?
a) 1, 2, 3, 4
b) 1, 2
c) 2, 3, 4
d) 3, 4
Answer
Answer: d [Reason:] 1) Is a variation of Turing Machine Halting problem and it is undecidable.
….2) Context Free Languages are not closed under intersection and complement.
….3) Complement of Regular languages is also regular.
….4) Recursive Languages is closed under complement.
8. Definition of a language L with alphabet {a} is given as following. L= { ank | k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?
a) k+1
b) n+1
c) 2n+1
d) 2k+1
Answer
Answer: b [Reason:] Note that n is a constant and k is any positive integer. For example, let n=3, then the DFA must be able to accept aaa, aaaaaa, aaaaaaaaa, , .. build such a DFA, 4 states are required.
Set 3
1. The graph that shows basic blocks and their successor relationship is called
a) Dag
b) Flow Graph
c) Control Graph
d) Hamilton Graph
Answer
Answer: b [Reason:] Flow graph shows the basic blocks.
2. The specific task storage manager performs
a) Allocation/ deal location of programs
b) Protection of storage area assigned to the program
c) Both of the mentioned
d) None of the mentioned
Answer
Answer: c [Reason:] Its basic function is that of the task storage manager.
3. When a computer is rebooted, a special type of loader is executed called
a) Compile and GO ” loader
b) Boot loader
c) Bootstrap Loader
d) Relating Loader
Answer
Answer: c [Reason:] A boot loader, is a small program that places the operating system (OS) of a computer into memory.
4. Disadvantage of ” Compile and GO ” loading scheme is that
a) Memory is wasted because the case occupied by the assembler is unavailable to the object program
b) Necessary to translate the users program
c) It is very difficult to handle multiple segments, even when the source programs are in different languages and to produce orderly modular programs
d) All of the mentioned
Answer
Answer: d [Reason:] In computer programming, a compile and go system, compile, load, and go system, assemble and go system, or load and go system[1][2][3] is a programming language processor in which the compilation, assembly, or link steps are not separated from program execution.
5. Function of the storage assignment is
a) Assign storage to all variables referenced in the source program
b) Assign storage to all temporary locations that are necessary for intermediate results
c) Assign storage to literals, and to ensure that the storage is allocated and appropriate locations are initialized
d) All of the mentioned
Answer
Answer: d [Reason:] The storage assignment performs the above mentioned tasks.
6. A non relocatable program is the one which
a) Cannot execute in any area of storage other than the one designated
b) Consists of a program and information for its relocation
c) None of the mentioned
d) All of the mentioned
Answer
Answer: a [Reason:] A non relocatable program is one which cannot be made to execute in any area of storage other than the one designated for it at the time of its coding or translation.
7. A relocatable program form is one which
a) Cannot execute in any area of storage other than the one designated
b) Consists of a program and information for its relocation
c) None of the mentioned
d) All of the mentioned
Answer
Answer: c [Reason:] A relocatable program form is one which consists of a program and relevant information for its relocation. Using this information it is possible to relocate the program to execute from a storage area then the one designated for it at the time of its coding or translation.
Set 4
1. A non relocatable program is the one which
a) Cannot execute in any area of storage other than the one designated
b) Consists of a program and information for its relocation
c) None of the mentioned
d) All of the mentioned
Answer
Answer: a [Reason:] A non reloadable program is one which cannot be made to execute in any area of storage other than the one designated for it at the time of its coding or translation.
2. A relocatable program form is one which
a) Cannot execute in any area of storage other than the one designated
b) Consists of a program and information for its relocation
c) None of the mentioned
d) All of the mentioned
Answer
Answer: c [Reason:] A relocatable program form is one which consists of a program and relevant information for its relocation. Using this information it is possible to relocate the program to execute from a storage area then the one designated for it at the time of its coding or translation.
3. A self-relocating program is one which
a) Cannot execute in any area of storage other than the one designated
b) Consists of a program and information for its relocation
c) None of the mentioned
d) All of the mentioned
Answer
Answer: c [Reason:] A self-relocating program is a program which can perform the relocation itself
•A table of information about address sensitive instruction in the program.
•Relocating logic that can perform the relocation of the address sensitive instructions
4. Scissoring enables
a) A part of data to be displayed
b) Entire data to be displayed
c) Full data display on full screen
d) No data to be displayed
Answer
Answer: a [Reason:] It displays a part of the data
5. Which of the following can be accessed by transfer vector approach of linking?
a) External data segments
b) External sub-routines
c) Data located in other procedure
d) All of the mentioned
Answer
Answer: b [Reason:] External subroutines are routines that are created and maintained separately from the program that will be calling them
6. Relocation bits used by relocating loader are specified by
a) Relocating loader itself
b) Linker
c) Assembler
d) Macro processor
Answer
Answer: b [Reason:] A linker or link editor is a computer 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.
7. Generation of intermediate code based on a abstract machine model is useful in compilers because
a) Implementation of lexical analysis and syntax analysis is made easier
b) Writing for intermediate code generation
c) Portability of the front end of the compiler
d) None of the mentioned
Answer
Answer: a [Reason:] Intermediate code generator receives input from its predecessor phase, semantic analyzer, in the form of an annotated syntax tree.
8. Which of the following module does not incorporate initialization of values changed by the module?
a) Non reusable module
b) Serially reusable module
c) Re-enterable module
d) All of the mentioned
Answer
Answer: a [Reason:] Non reusable models can be used once for a purpose they can’t be modified and used again
9. An intermediate code form is
a) Postfix Notation
b) Syntax Trees
c) Three address
d) All of the mentioned
Answer
Answer: d [Reason:] All the specified options are type of intermediate code form
10. The best way to compare the different implementations of symbol table is to compare the time required to
a) Add a new name
b) Make an enquiry
c) Add a new name and make an enquiry
d) All of the mentioned
Answer
Answer: d [Reason:] These are the different implementations of the symbol table as mentioned above.
Set 5
1. The idea of an automation with a stack as auxiliary storage
a) Finite automata
b) Push Down Automata
c) Deterministic Automata
d) None of the mentioned
Answer
Answer: b [Reason:] Push Down Automata manipulate the Stack as a part of performing a transition.
2. Transition of finite automata is
a) Finite Diagram
b) State Diagram
c) Node Diagram
d) E-R Diagram
Answer
Answer: b [Reason:] Transition of finite automata is Finite Diagram.
3. A context free language is called ambiguous if
a) It has 2 or more than 2 left derivations for some terminal string ѡ є L (G)
b) It has 2 or more than 2 left derivations for some terminal string ѡ є L (G)
c) Both of the mentioned
d) None of the mentioned
Answer
Answer: c [Reason:] When two or more Left and right most derivative occur the grammar turn ambiguous.
4. Which of the following statement is true?
a) Every language that is defined by regular expression can also be defined by finite automata
b) Every language defined by finite automata can also be defined by regular expression
c) We can convert regular expressions into finite automata
d) All of the mentioned
Answer
Answer: d [Reason:] All these statements are true w.r.t regular expression.
5. Which of the following identity is wrong?
a) R + R = R
b) (R*)* = R*
c) ɛR = Rɛ = R
d) ØR = RØ = RR*
Answer
Answer: d [Reason:] Regular grammar combined with empty does not give R* instead gives empty.
6. Grammars that can be translated to DFAs
a) Left linear grammar
b) Right linear grammar
c) Generic grammar
d) All of the mentioned
Answer
Answer: b [Reason:] Right Linear grammar can be translate to DFA.
7. A language is regular if and only if it is accepted by finite automata
a) The given statement statement is true
b) Given statement is false
c) Statement is partially true
d) None of the mentioned
Answer
Answer: a [Reason:] Regular Language is accepted by Finite Automata. Every regular language is Context free.
8. A Push Down Automata is if there is at most one transition applicable to each configuration
a) Deterministic
b) Non deterministic
c) Finite
d) Non finite
Answer
Answer: a [Reason:] In every situation only one transition is available as continuation then the result is deterministic push down automata.
Total Views: 20
