250+ TOP MCQs on Pumping Lemma for Regular Language

Automata Theory Multiple Choice Questions on “Pumping Lemma for Regular Language”.

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: b
Clarification: 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: c
Clarification: 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: b
Clarification: 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: b
Clarification: 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: a
Clarification: 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: b
Clarification: 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: d
Clarification: 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. 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: a
Clarification: Given: w =xyz. Here, xyz individually represents strings or rather substrings which we compute over conditions to check the regularity of the language.

9. 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: b
Clarification: 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.

250+ TOP MCQs on PDA-acceptance by Empty Stack and Answers

Automata Theory Multiple Choice Questions on “PDA-acceptance by Empty Stack”.

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: c
Clarification: 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: a
Clarification: 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: c
Clarification: 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: d
Clarification: 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: b
Clarification: 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: c
Clarification: 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: c
Clarification: 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: a
Clarification: 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: b
Clarification: 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: a
Clarification: NPDA stands for non-deterministic push down automata whereas DPDA stands for deterministic push down automata.

250+ TOP MCQs on The Language of Turing Machine

Automata Theory Multiple Choice Questions on “The Language of Turing Machine”.

1. A turing machine that is able to simulate other turing machines:
a) Nested Turing machines
b) Universal Turing machine
c) Counter machine
d) None of the mentioned

Answer: b
Clarification: A more mathematically oriented definition with the same universal nature was introduced by church and turing together called the Church-Turing thesis(formal theory of computation).

2. Which of the problems are unsolvable?
a) Halting problem
b) Boolean Satisfiability problem
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: Alan turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

3. Which of the following a turing machine does not consist of?
a) input tape
b) head
c) state register
d) none of the mentioned

Answer: d
Clarification: A state register is one which stores the state of the turing machine, one of the finitely many. Among these is the special start state with which the state register is initialized.

4. The value of n if turing machine is defined using n-tuples:
a) 6
b) 7
c) 8
d) 5

Answer: b
Clarification:
The 7-tuple definition of turing machine: (Q, S, G, d, q0, B, F)
where Q= The finite set of states of finite control
S= The finite set of input symbols
G= The complete set of tape symbols
d= The transition function
q0= The start state, a member of Q, in which the finite control is found initially.
B= The blank symbol
F= The set of final or accepting states, a subset of Q.

5. If d is not defined on the current state and the current tape symbol, then the machine ______
a) does not halts
b) halts
c) goes into loop forever
d) none of the mentioned

Answer: b
Clarification: If we reach hA or hR, we say TM halts. Once it has halted, it cannot move further, since d is not defined at any pair (hA,X) or (hR,X) where hA = accept halting state and hR = reject halting state.

6. Statement: Instantaneous descriptions can be designed for a Turing machine.
State true or false:
a) true
b) false

Answer: a
Clarification: Inorder to describe formally what a Turing machine does, we need to develop a notation for configurations or Instantaneous descriptions(ID).

7. Which of the following are the models equivalent to Turing machine?
a) Multi tape turing machine
b) Multi track turing machine
c) Register machine
d) All of the mentioned

Answer: d
Clarification: Many machines that might be thought to have more computational capability than a simple UTM can be shown to have no more power. They might compute faster or use less memory but cannot compute more powerfully i.e. more mathematical questions.

8. Which among the following is incorrect for o-machines?
a) Oracle Turing machines
b) Can be used to study decision problems
c) Visualizes Turing machine with a black box which is able to decide cerain decion problems in one operation
d) None of the mentioned

Answer: d
Clarification: In automata theory, an o- machine or oracle machine is a abstract machine used to study decision problems. The problem the oracle solves can be of any complexity class. Even undecidable problems like halting problems can be used.

9. RASP stands for:
a) Random access storage program
b) Random access stored program
c) Randomly accessed stored program
d) Random access storage programming

Answer: b
Clarification: RASP or Random access stored program is an abstract machine that has instances like modern stored computers.

10. Which of the following is not true about RASP?
a) Binary search can be performed more quickly using RASP than a turing machine
b) Stores its program in memory external to its state machines instructions
c) Has infinite number of distinguishable, unbounded registers
d) Binary search can be performed less quickly using RASP than a turing machine
e) More than two options are incorrect

Answer: d
Clarification: In theoretical computer science, the random access stored program( RASP ) machine model is an abstract machine used for the purpose of algorithm development and algorithm complexity theory.

11. State true or false:
Statement: RASP is to RAM like UTM is to turing machine.
a) true
b) false

Answer: a
Clarification: The Rasp is a random access machine model that, unlike the RAM has its program in its registers together with its input. The registers are unbounded(infinite in capacity); whether the number of registers is finite is model-specific.

250+ TOP MCQs on Randomized Algorithm and Answers

Automata Theory Multiple Choice Questions on “Randomized Algorithm”

1. A randomized algorithm uses random bits as input inorder to achieve a _____________ good performance over all possible choice of random bits.
a) worst case
b) best case
c) average case
d) none of the mentioned

Answer: c
Clarification: A randomized algorithm is an algorithm that employs a degree of randomness as a part of its logic using random bits as inputs and in hope of producing average case good performace.

2. Which of the following options match the given statement:
Statement: The algorithms that use the random input to reduce the expected running time or memory usage, but always terminate with a correct result in a bounded amount of time.
a) Las Vegas Algorithm
b) Monte Carlo Algorithm
c) Atlantic City Algorithm
d) None of the mentioned

Answer: a
Clarification: The other type of algorithms are probabalistic algorithms, which depending upon the random input, have a chance of producing incorrect results or fail to produce a result.

3. Which of the following are probalistic algorithms?
a) Las Vegas Algorithm
b) Monte Carlo Algorithm
c) Atlantic City Algorithm
d) All of the mentioned

Answer: d
Clarification: Monte Carlo algorithms are very vast, but only probably correct. On thr other side, Las Vegas algorithms are always correct, but probably fast.

4. Which of the following algorithms are probably correct as well as fast?
a) Las Vegas Algorithm
b) Monte Carlo Algorithm
c) Atlantic City Algorithm
d) All of the mentioned

Answer: c
Clarification: The atlantic city algorithms which are bounded polynomial time algorithms are probably correct and probably fast. It is correct more than 75% of the times.

5. Prisonner’s dilemma can be related to the following:
a) cooperative behaviour
b) graph theory
c) Both (a) and (b)
d) None of the mentioned

Answer: a
Clarification: Prisonner’s dilemma is a standard example of a game analysed in game theory where rational cooperative behaviour is judged on the basis of rewards and punishment.

6. Unix sort command uses _________ as its sorting technique.
a) Quick Sort
b) Bucket Sort
c) Radix Sort
d) Merge Sort

Answer: a
Clarification: Quicksort is the method of choice in many applications( Unix sort command) with O(nlogn) in worst case.

7. State true or false:
Statement: A turing machine has the capability of using randomly ‘generated’ numbers.
a) true
b) false

Answer: a
Clarification: Complexity theories models randomized algorithms as probalistic turing machines. A probalistic turing machine is a non deterministic turing machine which randomly chooses between the available transitions at each point according to some probalistic distribution.

8. For the given algorithm, find the probability of finding after k iterations:

find_a(array A, n, k)
begin
   i=0
     repeat
           Randomly select one element out of n elements
           i=i+1
     until i=k or a is found
end

a) (1/2)k
b) (1-(1/3))k
c) 1-(1/2)k
d) None of the mentioned

Answer: c
Clarification: The given is known as Monte Carlo Algorithm. If a is fount, the algorithm succeeds, else the algorith fails. The algorithm doesn not guarantee success but the run time is bounded.

9. Which of the following can be solved in computer science?
a) P=BPP problem
b) NP=co-NP problem
c) Do one way problems exist?
d) All of the mentioned

Answer: d
Clarification: There exists a list of unsolved problems in computational theory which includes many problems including the ones given.

10. Which of the following can be referred to as applications of Randomized algorithm?
a) Quicksort
b) Min Cut
c) Verifying Matrix Multiplication
d) All of the mentioned

Answer: d
Clarification: Freivalds algorithm is a probabalistic randomized algorithm we use to verify matrix multiplication. On the other hand, Randomness can be useful in quicksort. If the algorithm selects pivot element uniformaly at random, it has a probably high probabilty of finishing the work in O(nlogn) time regardless of the input.

250+ TOP MCQs on Uses of Epsilon-Transitions and Answers

Automata Theory Multiple Choice Questions on “Uses of Epsilon-Transitions”.

1. The automaton which allows transformation to a new state without consuming any input symbols:
a) NFA
b) DFA
c) NFA-l
d) All of the mentioned

Answer: c
Clarification: NFA-l or e-NFA is an extension of Non deterministic Finite Automata which are usually called NFA with epsilon moves or lambda transitions.

2. e-transitions are
a) conditional
b) unconditional
c) input dependent
d) none of the mentioned

Answer: b
Clarification: An epsilon move is a transition from one state to another that doesn’t require any specific condition.

3. The __________ of a set of states, P, of an NFA is defined as the set of states reachable from any state in P following e-transitions.
a) e-closure
b) e-pack
c) Q in the tuple
d) None of the mentioned

Answer: a
Clarification: The e-closure of a set of states, P, of an NFAis defined as the set of states reachable from any state in P following e-transitions.

4. The e-NFA recognizable languages are not closed under :
a) Union
b) Negation
c) Kleene Closure
d) None of the mentioned

Answer: The languages which are recognized by an epsilon Non deterministic automata are closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Negation
e) Star
f) Kleene closure

5. Is the language preserved in all the steps while eliminating epsilon transitions from a NFA?
a) yes
b) no

Answer: a
Clarification: Yes, the language is preserved during the dteps of construction: L(N)=L(N1)=L(N2)=L(3).

6. An e-NFA is ___________ in representation.
a) Quadruple
b) Quintuple
c) Triple
d) None of the mentioned

Answer: b
Clarification: An e-NFA consist of 5 tuples: A=(Q, S, d, q0, F)
Note: e is never a member of S.

7. State true or false:
Statement: Both NFA and e-NFA recognize exactly the same languages.
a) true
b) false

Answer: a
Clarification: e-NFA do come up with a convenient feature but nothing new.They do not extend the class of languages that can be represented.

250+ TOP MCQs on Applications of Pumping Lemma/Pigeonhole principle

Automata Theory Multiple Choice Questions on “Applications of Pumping Lemma/Pigeonhole principle”.

1. Which kind of proof is used to prove the regularity of a language?
a) Proof by contradiction
b) Direct proof
c) Proof by induction
d) None of the mentioned

Answer: a
Clarification: We use the method of proof by contradiction in pumping lemma to prove that a language is regular or not.

2. The language of balanced paranthesis is
a) regular
b) non regular
c) may be regular
d) none of the mentioned

Answer: b
Clarification: Given n, there is a string of balanced parentheses that begins with more than p left parentheses, so that y will contain entirely of left parentheses. By repeating y, we can produce a string that does not contain the same number of left and right parentheses, and so they cannot be balanced.

3. State true or false:
Statement: Pumping lemma gives a necessary but not sufficient condition for a language to be regular.
a) true
b) false

Answer: a
Clarification: The converse of the lemma is not true. There may exists some language which satisfy all the conditions of the lemma and still be non-regular.

4. Which of the following is/are an example of pigeon hole principle?
a) Softball team
b) Sock picking
c) Hair counting
d) All of the mentioned

Answer: d
Clarification: There are several applications of pigeonhole principle:
Example: The softball team: Suppose 7 people who want to play softball(n=7 items), with a limitation of only 4 softball teams to choose from. The pigeonhole principle tells us that they cannot all play for different teams; there must be atleast one team featuring atleast two of the seven players.

5. Pigeonhole principle can be applied in the following computer science algorithms:
a) hashing algorithm
b) lossless compression algorithm
c) both (a) and (b)
d) none of the mentioned

Answer: c
Clarification: Collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array.

6. If n objects are distributed over m places, and n < m, then some of the places receive:
a) at least 2 objects
b) at most 2 objects
c) no object
d) none of the mentioned

Answer: c
Clarification: This is one of the alternative formulations of the pigeon hole principle. As n < m, there will exist some place which will not receive any of the object.

7. Which of the following fields may have pigeonhole principle violated?
a) Discrete mathematics
b) Computer Science
c) Quantum Mechanics
d) None of the mentioned

Answer: c
Clarification: Y Aharonov proved mathematically the violation of pigeon hole principle in Quantum mechanics and proposed inferometric experiments to test it.

8. Which of the following is not an application of Pumping Lemma?
a) {0i1i|i>=0}
b) {0ix|i>=0, x∈{0, 1}* and |x|<=i}
c) {0n| n is prime}
d) None of the mentioned

Answer: d
Clarification: None of the mentioned are regular language and are an application to the technique Pumping Lemma. Each one of the mentioned can be proved non regular using the steps in Pumping lemma.

9. Which of the following can refer a language to be non regular?
a) Pumping Lemma
b) Myphill Nerode
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: On the contrary, the typical way to prove that a language is to construct either a finite state machine or a regular expression for the language.

10. Which of the following is not an example of counting argument?
a) Pigeonhole principle
b) Dirichlet’s drawer principle
c) Dirichlet’s box principle
d) None of the mentioned

Answer: d
Clarification: Pigeon hole principle or Dirichlet’s drawer principle or Dirichlet’s box principle is an example of counting argument whose field is called Combinatorics.