Multiple choice question for engineering
Set 1
1. A finite automaton accepts which type of language:
a) Type 0
b) Type 1
c) Type 2
d) Type 3
Answer
Answer: d [Reason:] Type 3 refers to Regular Languages which is accepted by a finite automaton.
2. Which among the following are incorrect regular identities?
a) εR=R
b) ε*=ε
c) Ф*=ε
d) RФ=R
Answer
Answer: d [Reason:] There are few identities over Regular Expressions which include: RФ=ФR=Ф≠R
3. Simplify the following regular expression:
ε+1*(011) *(1*(011) *) *
a) (1+011) *
b) (1*(011) *)
c) (1+(011) *) *
d) (1011) *
Answer
Answer: a [Reason:] ε+1*(011) *(1*(011) *) *
ε + RR*= ε + R*R= ε + R+= R*
4. P, O, R be regular expression over ∑, P is not ε, then
R=Q + RP has a unique solution:
a) Q*P
b) QP*
c) Q*P*
d) (P*O*) *
Answer
Answer: b [Reason:] The given statement is the Arden’s Theorem and it tends to have a unique solution as QP*.
Let P and Q be regular expressions,
R=Q+RP
R=Q+(Q+RP) P
R=Q+((Q+RP) +RP) +P=Q+QP+RPP+RPP=Q+QP+(Q+RP) PP+(Q+RP) PP=Q+QP+QPP+RPPP+QPP+RPPP,
If we do this recursively, we get:
R= QP*
5. Arden’s theorem is true for:
a) More than one initial states
b) Null transitions
c) Non-null transitions
d) None of the mentioned
Answer
Answer: c [Reason:] Arden’s theorem strictly assumes the following;
a) No null transitions in the transition diagrams
b) True for only single initial state
6. The difference between number of states with regular expression (a + b) and (a + b) * is:
a) 1
b) 2
c) 3
d) 0
Answer
Answer: a [Reason:]
7. In order to represent a regular expression, the first step to create the transition diagram is:
a) Create the NFA using Null moves
b) Null moves are not acceptable, thus should not be used
c) Predict the number of states to be used in order to construct the Regular expression
d) None of the mentioned
Answer
Answer: a [Reason:] Two steps are to be followed while converting a regular expression into a transition diagram:
a) Construct the NFA using null moves.
b) Remove the null transitions and convert it into its equivalent DFA.
8. (0+ε) (1+ε) represents
a) {0, 1, 01, ε}
b) {0, 1, ε}
c) {0, 1, 01 ,11, 00, 10, ε}
d) {0, 1}
Answer
Answer: a [Reason:] The regular expression is fragmented and the set of the strings eligible is formed. ‘+’ represents union while ‘.’ Represents concatenation.
9. The minimum number of states required to automate the following Regular Expression:
(1) *(01+10) (1) *
a) 4
b) 3
c) 2
d) 5
Answer
Answer: a
10. Regular Expression denote precisely the ________ of Regular Language.
a) Class
b) Power Set
c) Super Set
d) None of the mentioned
Answer
Answer: a [Reason:] Regular Expression denote precisely the class of regular language. Given any regular expression, L(R) is a regular language. Given any regular language L, there is a regular expression R, such that L(R)=L.
Set 2
1. If two sets, R and T has no elements in common i.e. RÇT=Æ, then the sets are called
a) Complement
b) Union
c) Disjoint
d) Connected
Answer
Answer: c [Reason:] Two sets are called disjoint if they have no elements in common i.e. RÇT=Æ.
2. Which among the following is not a part of the Context free grammar tuple?
a) End symbol
b) Start symbol
c) Variable
d) Production
Answer
Answer: a [Reason:] The tuple definition of context free grammar is: (V, T, P, S) where V=set of variables, T=set of terminals, P=production, S= Starting Variable.
3. A context free grammar is a ___________
a) English grammar
b) Regular grammar
c) Context sensitive grammar
d) None of the mentioned
Answer
Answer: c [Reason:] Context free grammar is the set which belongs to the set of context free grammar. Similarly, Regular grammar is a set which belongs to the the set of Context free grammar.
4. The closure property of context free grammar includes :
a) Kleene
b) Concatenation
c) Union
d) All of the mentioned
Answer
Answer: d [Reason:] Context free grammars are closed under kleene operation, union and concatenation too.
5. Which of the following automata takes stack as auxiliary storage?
a) Finite automata
b) Push down automata
c) Turing machine
d) All of the mentioned
Answer
Answer: b [Reason:] Pushdown Automaton uses stack as an auxiliary storage for its operations. Turing machines use Queue for the same.
6. Which of the following automata takes queue as an auxiliary storage?
a) Finite automata
b) Push down automata
c) Turing machine
d) All of the mentioned
Answer
Answer: c [Reason:] Pushdown Automaton uses stack as an auxiliary storage for its operations. Turing machines use Queue for the same.
7. A context free grammar can be recognized by
a) Push down automata
b) 2 way linearly bounded automata
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] A linearly bounded automata is a restricted non deterministic turing machine which is capable of accepting ant context free grammar.
8. A null production can be referred to as:
a) String
b) Symbol
c) Word
d) All of the mentioned
Answer
Answer: a [Reason:] Null production is always taken as a string in computational theory.
9. The context free grammar which generates a Regular Language is termed as:
a) Context Regular Grammar
b) Regular Grammar
c) Context Sensitive Grammar
d) None of the mentioned
Answer
Answer: b [Reason:] Regular grammar is a subset of Context free grammar. The CFGs which produces a language for which a finite automaton can be created is called Regular grammar.
10. NPDA stands for
a) Non-Deterministic Push Down Automata
b) Null-Push Down Automata
c) Nested Push Down Automata
d) All of the mentioned
Answer
Answer: a [Reason:] NPDA stands for non-deterministic push down automata whereas DPDA stands for deterministic push down automata.
Set 3
1. All set of polynomial questions which can be solved by a turing machine using a polynomial amount of space:
a) PSPACE
b) NPSPACE
c) EXPSPACE
d) None of the mentioned
Answer
Answer: a [Reason:] PSPACE is the problem class which contains all set of decision problems which can be solved using a turing machine taking polynomial amount of space.
2. PSPACE is strictly the super set of:
a) Regular language
b) Context free language
c) Context Sensitive Language
d) None of the mentioned
Answer
Answer: c [Reason:] Membership of a string in a language defined by an arbitrary context sensitive grammar, or by an arbitrary determinisic context sensitive grammar, is a PSPACE -complete problem.
3. Savitch theorem relates to which of the following:
a) PSPACE=NPSPACE
b) Alternating Turing Machine
c) Time complexity
d) None of the mentioned
Answer
Answer: a [Reason:] Some important conclusions of Savitch theorem includes:
a) PSPACE=NPSPACE: square of a polynomial function is still a polynomial function.
b) NL∈L2
4. The class PSPACE is closed under the following operations:
a) Union
b) Concatenation
c) Kleene
d) All of the mentioned
Answer
Answer: d [Reason:] The closure property of PSPACE class includes :- Union, Concatenation and Kleene operation.
5. Correct the given order:
NL∈ P∈ NP∈ PH∈ PSPACE
a) NP∈ P∈ NL∈ PH∈ PSPACE
b) NL∈ PH∈ NP∈ P∈ PSPACE
c) NL∈ P∈ NP∈ PH∈ PSPACE
d) None of the mentioned
Answer
Answer: c [Reason:] The given order is the only correct order and further PSPACE belongs to EXPTIME class and subsequently occurs EXPSPACE class.
6. NL ∈ PSPACE ∈ EXPSPACE
The given relation involves which of the following theorems?
a) Space hierarchy theorem
b) Savitch’s theorem
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] From space hierarchy theorem: NL ∈ NPSPACE, from Savitch’s theorem: NPSPACE= PSPACE.
7. Statement : All PSPACE problems can be reduced to PSPACE-complete problems.
State true or false:
a) true
b) false
Answer
Answer: a [Reason:] PSPACE-complete problems are the most difficut problems is PSPACE. Finding a simple solution to PSPACE-complete means simple solution to all other problems in PSPACE because all PSPACE problems can be reduced to PSPACE-complete problems.
8. Without needing extra __________ we can simulate non deterministic turing machine using deterministic turing machine.
a) time
b) space
c) both time and space
d) none of the mentioned
Answer
Answer: b [Reason:] Though it may use extra time, but as PSPACE=NPSPACE from savitch’s theorem, we can say that space taken is same for both the machins, deterministic as well as non-deterministic.
9. Complement of all the problems in PSPACE is ________
a) PSPACE
b) NL
c) P
d) All of the mentioned
Answer
Answer: a [Reason:] The complement of all the problems in PSPACE are also in PSPACE, meaning co-PSPACE= PSPACE.
10. Which of the following PSPACE can be characterized into?
a) APTIME
b) AP
c) Quantom complexity class
d) None of the mentioned
Answer
Answer: d [Reason:] An alternative characterization of PSPACE is a set of problems decidable by a turing machine in polynomial time, sometimes called, APTIME or AP.
Set 4
1. A turing machine has ____________ number of states in a CPU.
a) finite
b) infinte
c) May be finite
d) None of the mentioned
Answer
Answer: a [Reason:] A turing machine has finite number of states in its CPU. However the states are not small in number. Real computer consist of registers which can store values (fixed number of bits).
2. Suppose we have a simple computer with control unit holding a PC with a 32 bit address + Arithmetic unit holding one double length 64 bit Arithmetic Register. The number of states the finite machine will hold:
a) 2(32*64)
b) 296
c) 96
d) 32
Answer
Answer: b [Reason:] According to the statistics of the question, we will have a finite machine with 2^96 states.
3. In one move a turing machine will:
a) Change a state
b) Write a tape symbol in the cell scanned
c) Move the tape head left or right
d) All of the mentioned
Answer
Answer: d [Reason:] A move of a turing machine is the function of the state of finite control and the tape symbol just scanned.
4. State true or false:
Statement: We can use the finite control of turing machine to hold a finite amount of data.
a) true
b) false
Answer
Answer: a [Reason:]
The finite control not only contains state q but also three data, A, B, C. The following technique requires no extension to the Turing Machine model. Shaping states this way allows to describe transitions in more systematic way and often to simplify the strategy of the program.
5. Statement 1: Multitrack Turing machine.
Statement 2: Gamma is Cartesian product of a finite number of finite sets.
Which among the following is the correct option?
a) Statement 1 is the assertion and Statement 2 is the reason
b) Statement 1 is the reason and Statement 2 is the assertion
c) Statement 1 and Statement 2 are independent from each other
d) None of the mentioned
Answer
Answer: a [Reason:] Cartesian product works like a struct in C/C++. For Example: Computer tape storage is something like 8 or 9 bits in each cell. One can recognize a multi track tape machine by looking at the transitions because each will have tuples as the read and write symbols.
6. A multi track turing machine can described as a 6-tuple (Q, X, S, d, q0, F) where X represents:
a) input alphabet
b) tape alphabet
c) shift symbols
d) none of the mentioned
Answer
Answer: b [Reason:] The 6-tuple (Q, X, S, d, q0, F) can be explained as:
Q represents finite set of states,
X represents the tape alphabet,
S represents the input alphabet
d represents the relation on states and the symbols
q0 represents the initial state
F represents the set of final states.
7. Which of the following statements are false?
a) A multi track turing machine is a special kind of multi tape turing machine
b) 4-heads move independently along 4-tracks in standard 4-tape turing machine
c) In a n-track turing machine, n head reads and writes on all the tracks simultaneously.
d) All of the mentioned
Answer
Answer: c [Reason:] In a n-track turing machine, one head reads and writes on all the tracks simultaneously.
8. State true or false:
Statement: Two track turing machine is equivalent to a standard turing machine.
a) true
b) false
Answer
Answer: a [Reason:] This can be generalized for n- tracks and can be proved equivalent using ennumerable languages.
9. Which of the following is/are not true for recursively ennumerable language?
a) partially decidable
b) Turing acceptable
c) Turing Recognizable
d) None of the mentioned
Answer
Answer: d [Reason:] In automata theory, a formal language is called recursively ennumerable language or partially decidable or semi decidable or turing acceptable or turing recognizable if there exists a turing machine which will ennumerate all valid strings of the language.
10. According to Chomsky hierarchy, which of the following is adopted by Recursively Ennumerable language?
a) Type 0
b) Type 1
c) Type 2
d) Type 3
Answer
Answer: a [Reason:] Recursively Ennumerable languages are type 0 languages in the Chomsky hierarchy. All regular, context free, context sensitive languages are recursivelyennumerable language.
Set 5
1. Relate the following statement:
Statement: All sufficiently long words in a regular language can have a middle section of words repeated a number of times to produce a new word which also lies within the same language.
a) Turing Machine
b) Pumping Lemma
c) Arden’s theorem
d) None of the mentioned
Answer
Answer: b [Reason:] Pumping lemma defines an essential property for every regular language in automata theory. It has certain rules which decide whether a language is regular or not.
2. While applying Pumping lemma over a language, we consider a string w that belong to L and fragment it into _________ parts.
a) 2
b) 5
c) 3
d) 6
Answer
Answer: c [Reason:] We select a string w such that w=xyz and |y|>0 and other conditions. However, there exists an integer n such that |w|>=n for any wÎL.
3. If we select a string w such that w∈L, and w=xyz. Which of the following portions cannot be an empty string?
a) x
b) y
c) z
d) all of the mentioned
Answer
Answer: b [Reason:] The lemma says, the portion y in xyz cannot be zero or empty i.e. |y|>0, this condition needs to be fulfilled to check the conclusion condition.
4. Let w= xyz and y refers to the middle portion and |y|>0.What do we call the process of repeating y 0 or more times before checking that they still belong to the language L or not?
a) Generating
b) Pumping
c) Producing
d) None of the mentioned
Answer
Answer: b [Reason:] The process of repeatation is called pumping and so, pumping is the process we perform before we check whether the pumped string belongs to L or not.
5. There exists a language L. We define a string w such that w∈L and w=xyz and |w| >=n for some constant integer n.What can be the maximum length of the substring xy i.e. |xy|<=?
a) n
b) |y|
c) |x|
d) none of the mentioned
Answer
Answer: a [Reason:] It is the first conditional statement of the lemma that states that |xy|<=n, i.e. the maximum length of the substring xy in w can be n only.
6. Fill in the blank in terms of p, where p is the maximum string length in L.
Statement: Finite languages trivially satisfy the pumping lemma by having n = ______
a) p*1
b) p+1
c) p-1
d) None of the mentioned
Answer
Answer: b [Reason:] Finite languages trivially satisfy the pumping lemma by having n equal to the maximum string length in l plus 1.
7. Answer in accordance to the third and last statement in pumping lemma:
For all _______ xyiz ∈L
a) i>0
b) i<0
c) i<=0
d) i>=0
Answer
Answer: d [Reason:] Suppose L is a regular language . Then there is an integer n so that for any x∈L and |x|>=n, there are strings u,v,w so that
x= uvw
|uv|<=n
|v|>0
for any m>=0, uvmw ∈L.
8. If d is a final state, which of the following is correct according to the given diagram?
a) x=p, y=qr, z=s
b) x=p, z=qrs
c) x=pr, y=r, z=s
d) All of the mentioned
Answer
Answer: a [Reason:] The FSA accepts the string pqrs. In terms of pumping lemma, the string pqrs is broken into an x portion an a, a y portion qr and a z portion s.
9. Let w be a string and fragmented by three variable x, y, and z as per pumping lemma. What does these variables represent?
a) string count
b) string
c) both (a) and (b)
d) none of the mentioned
Answer
Answer: a [Reason:] Given: w =xyz. Here, xyz individually represents strings or rather substrings which we compute over conditions to check the regularity of the language.
10. Which of the following one can relate to the given statement:
Statement: If n items are put into m containers, with n>m, then atleast one container must contain more than one item.
a) Pumping lemma
b) Pigeon Hole principle
c) Count principle
d) None of the mentioned
Answer
Answer: b [Reason:] Pigeon hole principle states the following example: If there exists n=10 pigeons in m=9 holes, then since 10>9, the pigeonhole principle says that at least one hole has more than one pigeon.
