Multiple choice question for engineering
Set 1
1. Under which of the following operation, NFA is not closed?
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned
Answer
Answer: d [Reason:] NFA is said to be closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Kleene
e) Negation
2. It is less complex to prove the closure properties over regular languages using
a) NFA
b) DFA
c) PDA
d) Can’t be said
Answer
Answer: a [Reason:] We use the construction method to prove the validity of closure properties of regular languages. Thus, it can be observe, how tedious and complex is the construction of a DFA as compared to an NFA with respect to space.
3. Which of the following is an application of Finite Automaton?
a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned
Answer
Answer: d [Reason:] There are many applications of finite automata, mainly in the field of Compiler Design and Parsers and Search Engines.
4. John is asked to make an automaton which accepts a given string for all the occurrence of ‘1001’ in it. How many number of transitions would John use such that, the string processing application works?
a) 9
b) 11
c) 12
d) 15
Answer
Answer: a [Reason:]
5. Which of the following do we use to form an NFA from a regular expression?
a) Subset Construction Method
b) Power Set Construction Method
c) Thompson Construction Method
d) Scott Construction Method
Answer
Answer: c [Reason:] Thompson Construction method is used to turn a regular expression in an NFA by fragmenting the given regular expression through the operations performed on the input alphabets.
6. Which among the following can be an example of application of finite state machine(FSM)?
a) Communication Link
b) Adder
c) Stack
d) None of the mentioned
Answer
Answer: a [Reason:] Idle is the state when data in form of packets is send and returns if NAK is received else waits for the NAK to be received.
7. Which among the following is not an application of FSM?
a) Lexical Analyser
b) BOT
c) State charts
d) None of the mentioned
Answer
Answer: d [Reason:] Finite state automation is used in Lexical Analyser, Computer BOT (used in games), State charts, etc.
8. L1= {w | w does not contain the string tr }
L2= {w | w does contain the string tr}
Given ∑= {t, r}, The difference of the minimum number of states required to form L1 and L2?
a) 0
b) 1
c) 2
d) Cannot be said
Answer
Answer: a [Reason:]
9. Predict the number of transitions required to automate the following language using only 3 states:
L= {w | w ends with 00}
a) 3
b) 2
c) 4
d) Cannot be said
Answer
Answer: a [Reason:]
10. The total number of states to build the given language using DFA:
L= {w | w has exactly 2 a’s and at least 2 b’s}
a) 10
b) 11
c) 12
d) 13
Answer
Answer: a [Reason:] We need to make the number of a as fixed i.e. 2 and b can be 2 or more. Thus, using this condition a finite automata can be created using 1 states.
Set 2
1. Which of the following are related to construction of One Tape turing machines?
a) JFLAP
b) NFLAP
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: a [Reason:] JFLAP is educational software written in java to experiment with the topics in automata theory and area of formal languages.
2. Which of the following topics cannot be covered using JFLAPS?
a) L-System
b) Unrestricted Grammar
c) Regular Expression
d) None of the mentioned
Answer
Answer: d [Reason:] Topics like regular expressions, context free languages and unrestricted grammar including parsers like LL,SLR parsers can be covered using JFLAPS.
3. State true or false:
Statement: Multitape turing machine have multi tapes where each tape is accessed with one head.
a) true
b) false
Answer
Answer: b [Reason:] Multitape turing machines do have multiple tapes but they they are accessed by separate heads.
4. Which of the following statements is/are true?
a) Every multitape turing machine has its equivalent single tape turing machine
b) Every multitape turing machine is an abstract machine
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] A multitape turing machine is an ordinary turing machine which is always abstract.And they do have their equivalent single tape turing machines.
5. Are Multitape and Multitrack turing machines same?
a) Yes
b) No
c) Somewhat yes
d) Cannot tell
Answer
Answer: a [Reason:] Multitrack turing machines are special types of Multitape turing machines. In a standard n-tape Turing machine, n heads move independently along n-tracks.
6. In a n-track turing machine, _________ head/heads read and write on all tracks simultaneously.
a) one
b) two
c) n
d) infinite
Answer
Answer: a [Reason:] In a n-track Turing machine, one head reads and writes on all tracks simultaneously. A tape position in a n-track Turing Machine contains n symbols from the tape alphabet.
7. Which of the following does not exists?
a) Turing Machine with Multiple heads
b) Turing Machine with infinite tapes
c) Turing machine with two dimensional tapes
d) None of the mentioned
Answer
Answer: d [Reason:] All of the mentioned are one or the other kind of Turing machines in existence.
8. Can a multitape turing machine have an infinte number of tapes?
a) Yes
b) No
Answer
Answer: b [Reason:] One needs a finite number of tapes. The proofs that show the equivalence between multi-tape TM and one-band TM rely on the fact that the number of tapes is bounded.
9. Every language accepted by a k-tape TM is _____ by a single-tape TM.
a) accepted
b) not accepted
c) generated
d) not generated
Answer
Answer: a [Reason:] Its the theorem that states Every multitape turing machine can be simulated by a single tape turing machine and the corresponding language can be accepted.
10. Which of the following is/are a basic TM equivalent to?
a) Multitrack TM
b) Multitape TM
c) Non-deterministic TM
d) All of the mentioned
Answer
Answer: d [Reason:] Tms can be used as both: language recognizers/Computers. TMs are like universal computing machines with universal storage.
Set 3
1. The decision problem is the function from string to ______________
a) char
b) int
c) boolean
d) none of the mentioned
Answer
Answer: c [Reason:] The decision problem requires checking of input (string) has some property or not. That is a string to boolean transaction.
2. A language L is said to be ____________ if there is a turing machine M such that L(M)=L and M halts at every point.
a) Turing acceptable
b) decidable
c) undecidable
d) none of the mentioned
Answer
Answer: b [Reason:] Decidability refers to the decision problem and existence of a effective method for determining membership, and return true and false accordingly rather that going into a loop forever.
3. Which aong the following are undecidable theories?
a) The first order theory of boolean algebra
b) The first order theory of Euclidean geomentry
c) The first order theory of hyperbolic geometry
d) The first order theory of the natural number with addition, multiplication, and equality
Answer
Answer: d [Reason:] Tarski and Mostowski in 1949, established that the first order theory of natural numbers with addition, multiplication, and equality is an undecidable theory. Others mentioned are decidable theories.
4. Rec-DFA = {
Fill in the blank:
Rec-DFA is ___________
a) Undecidable
b) Decidable
c) Non finite
d) None of the mentioned
Answer
Answer: b [Reason:] Under decidablity of regular language properties we have the following lemma which states that A DFA which recognizes an input w is decidable.
5. Which among the following are semi decidable?
a) Empty-DFA
b) Rec-NFA
c) Infinite-DFA
d) All of the mentioned
Answer
Answer: d [Reason:] All are the properties of regular languages and all are decidable languages.
6. The language accepted by a turing machine is called ____________
a) Recursive Ennumerable
b) Recursive
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] The language accepted by Turing machines are called recursively ennumerable (RE), and the subset of RE languages that are accepted by a turing machine that always halts are called recursive.
7. Decidable can be taken as a synonym to:
a) recursive
b) non recursive
c) recognizable
d) none of the mentioned
Answer
Answer: a [Reason:] We can refer to languages as ‘recursive’ and problems as ‘decidable’. If a language is not recursive , then we call the problem expressed by that language undecidable.
8. The problems which have no algorithm, regardless of whether or not they are accepted by a turing machine that fails to halts on some input are referred as:
a) Decidable
b) Undecidable
c) Computable
d) None of the mentioned
Answer
Answer: b [Reason:] The problems that can be solved by a turing machine can divided into two classes:
a) Those that have an algorithm
b) Intractable problems: Those that are only solved by a turing machine that may run forever on inputs they do not accept.
9. An algorithm is called efficient if it runs in ____________ time on a serial computer.
a) polynomial
b) non polynomial
c) logarithmic
d) none of the mentioned
Answer
Answer: a [Reason:] Example: Runtimes of efficient algorithms
O(n), O(nlogn), O(n3log2n)
Runtimes of inefficient algorithms
O(2n), O(n!)
10. A problem is called __________ if its has an efficient algorithm for itself.
a) tractable
b) intractable
c) computational
d) none of the mentioned
Answer
Answer: a [Reason:] A problem is called intractable iff there is an efficient (i.e. polynomial time) algorithm that solves it. A problem is called intractable iff there exists no efficient algorithm that solves it.
11. A formal language is recursive if :
a) a total turing machine exists
b) a turing machine that halts for every input
c) turing machine rejects if the input does not belong to the language
d) all of the mentioned
Answer
Answer: d [Reason:] A formal language is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.
12. Recursive languages are also known as:
a) decidable
b) undecidable
c) sometimes decidable
d) none of the mentioned
Answer
Answer: a [Reason:] A language is recursive if there exists a turing machine such that it halts i.e. accepts if the input belongs to the language else rejects. It is better called Turing decidable language.
13. The class of recursive language is known as:
a) R
b) RC
c) RL
d) All of the mentioned
Answer
Answer: a [Reason:] R is the set of all recursive languages, a class of decision problems solvable by turing machines. Although, R is also used for the class RP.
14. Which of the following was not a part of Chomsky hierarchy ?
a) Context sensitive grammar
b) Unrestricted grammar
c) Recursive grammar
d) None of the mentioned
Answer
Answer: c [Reason:] All recursive languages are recursively enumerable. All regular, context free and context sensitive languages are recursive.
Set 4
1. The number of tuples in an extended Non Deterministic Finite Automaton:
a) 5
b) 6
c) 7
d) 4
Answer
Answer: a [Reason:] For NFA or extended transition function on NFA, the tuple elements remains same i.e. 5.
2. Choose the correct option for the given statement:
Statement: The DFA shown represents all strings which has 1 at second last position.
a) Correct
b) Incorrect, Incomplete DFA
c) Wrong proposition
d) May be correct
Answer
Answer: c [Reason:] The given figure is an NFA. The statement contradicts itself.
3. What is wrong in the given definition?
Def: ({q0, q1, q2}, {0,1}, δ, q3, {q3})
a) The definition does not satisfy 5 Tuple definition of NFA
b) There are no transition definition
c) Initial and Final states do not belong to the Graph
d) Initial and final states can’t be same
Answer
Answer: c [Reason:] q3 does not belong to Q where Q= set of finite states.
4. If δ is the transition function for a given NFA, then we define the δ’ for the DFA accepting the same language would be:
Note: S is a subset of Q and a is a symbol.
a) δ’ (S, a) =Upϵs δ (p, a)
b) δ’ (S, a) =Up≠s δ (p, a)
c) δ’ (S, a) =Upϵs δ(p)
d) δ’ (S) =Up≠s δ(p)
Answer
Answer: a [Reason:] According to subset construction, equation 1 holds true.
5. What is the relation between DFA and NFA on the basis of computational power?
a) DFA > NFA
b) NFA > DFA
c) Equal
d) Can’t be said
Answer
Answer: c [Reason:] DFA is said to be a specific case of NFA and for every NFA that exists for a given language, an equivalent DFA also exists.
6. If a string S is accepted by a finite state automaton, S=s1s2s3……sn where siϵ∑ and there exists a sequence of states r0, r1, r2…… rn such that δ(r(i), si+1) =ri+1 for each 0, 1, …n-1, then r(n) is:
a) initial state
b) transition symbol
c) accepting state
d) intermediate state
Answer
Answer: c [Reason:] r(n) is the final state and accepts the string S after the string being traversed through r(i) other states where I ϵ 01,2…(n-2).
7. According to the given table, compute the number of transitions with 1 as its symbol but not 0:
a) 4
b) 3
c) 2
d) 1
Answer
Answer: d [Reason:] The transition graph is made and thus the answer can be found.
8. From the given table, δ*(q0, 011) =?
a) {q0}
b) {q1} U {q0, q1, q2}
c) {q2, q1}
d) {q3, q1, q2, q0}
Answer
Answer: b [Reason:] δ*(q0,011) = Urϵδ*(q0,01) δ (r, 1) = {q0, q1, q2}.
9. Number of times the state q3 or q2 is being a part of extended 6 transition state is
a) 6
b) 5
c) 4
d) 7
Answer
Answer: a [Reason:] According to the question, presence of q2 or q1 would count so it does and the answer according to the diagram is 6.
10. Predict the missing procedure:
1.Δ(Q0, ε) ={Q0},
2.Δ(Q0, 01) = {Q0, Q1}
3.δ(Q0, 010) =?
a) {Q0, Q1, Q2}
b) {Q0, Q1}
c) {Q0, Q2}
d) {Q1, Q2}
Answer
Answer: c [Reason:] According to given table and extended transition state implementation, we can find the state at which it rests.
Set 5
1. Assume the R is a relation on a set A, aRb is partially ordered such that a and b are _____________
a) reflexive
b) transitive
c) symmetric
d) reflexive and transitive
Answer
Answer: d [Reason:] A partially ordered relation refers to one which is Reflexive, Transitive and Antisymmetric.
2. The non- Kleene Star operation accepts the following string of finite length over set A = {0,1} | where string s contains even number of 0 and 1
a) 01,0011,010101
b) 0011,11001100
c) ε,0011,11001100
d) ε,0011,11001100
Answer
Answer: b [Reason:] The Kleene star of A, denoted by A*, is the set of all strings obtained by concatenating zero or more strings from A.
3. A regular language over an alphabet ∑ is one that cannot be obtained from the basic languages using the operation
a) Union
b) Concatenation
c) Kleene*
d) All of the mentioned
Answer
Answer: d [Reason:] Union, Intersection, Concatenation, Kleene*, Reverse are all the closure properties of Regular Language.
4. Statement 1: A Finite automata can be represented graphically; Statement 2: The nodes can be its states; Statement 3: The edges or arcs can be used for transitions
Hint: Nodes and Edges are for trees and forests too.
Which of the following make the correct combination?
a) Statement 1 is false but Statement 2 and 3 are correct
b) Statement 1 and 2 are correct while 3 is wrong
c) None of the mentioned statements are correct
d) All of the mentioned
Answer
Answer: d [Reason:] It is possible to represent a finite automaton graphically, with nodes for states, and arcs for transitions.
5. The minimum number of states required to recognize an octal number divisible by 3 are/is
a) 1
b) 3
c) 5
d) 7
Answer
Answer: b [Reason:] According to the question, minimum of 3 states are required to recognize an octal number divisible by 3.
6. Which of the following is a not a part of 5-tuple finite automata?
a) Input alphabet
b) Transition function
c) Initial State
d) Output Alphabet
Answer
Answer: d [Reason:] A FA can be represented as FA= (Q, ∑, δ, q0, F) where Q=Finite Set of States, ∑=Finite Input Alphabet, δ=Transition Function, q0=Initial State, F=Final/Acceptance State).
7. If an Infinite language is passed to Machine M, the subsidiary which gives a finite solution to the infinite input tape is ______________
a) Compiler
b) Interpreter
c) Loader and Linkers
d) None of the mentioned
Answer
Answer: a [Reason:] A Compiler is used to give a finite solution to an infinite phenomenon. Example of an infinite phenomenon is Language C, etc.
8. The number of elements in the set for the Language L={xϵ(∑r) *|length if x is at most 2} and ∑={0,1} is_________
a) 7
b) 6
c) 8
d) 5
Answer
Answer: a [Reason:] ∑r= {1,0} and a Kleene* operation would lead to the following set=COUNT{ε,0,1,00,11,01,10} =7.
9. For the following change of state in FA, which of the following codes is an incorrect option?
a) δ (m, 1) =n
b) δ (0, n) =m
c) δ (m,0) =ε
d) s: accept = false; cin >> char;
if char = “0” goto n;
Answer
Answer: b [Reason:] δ(QX∑) = Q1 is the correct representation of change of state. Here, δ is called the Transition function.
10. Given: ∑= {a, b}
L= {xϵ∑*|x is a string combination}
∑4 represents which among the following?
a) {aa, ab, ba, bb}
b) {aaaa, abab, ε, abaa, aabb}
c) {aaa, aab, aba, bbb}
d) All of the mentioned
Answer
Answer: b [Reason:] ∑* represents any combination of the given set while ∑x represents the set of combinations with length x where x ϵ I.
Total Views: 21
