+1-315-636-4485
+91 98151-74050 
This quiz contains multiple-choice problems on the pumping lemma for regular language and its applications, reversal and inverse homomorphism, conversions and testing emptiness.
Let w be a string and fragmented by three variables x, y, and z per the pumping lemma. What do these variables represent?
String count
String
String count and string
None of the above
Answer in accordance to the third and last statement in pumping lemma: For all __, xyiz ∈ L.
i > 0
i < 0
i <= 0
i >= 0
Fill in the blank in terms of p, where p is the maximum string length in L: Finite languages trivially satisfy the pumping lemma by having n = __.
p*1
p+1
p-1
None of the above
There exists a language L. We define a string w such that w ∈ L and w = xyz and |w| >= n for constant integer n. What can be the maximum length of the substring xy, i.e. |xy| <=?
n
|y|
|x|
None of the above
Let w= xyz, with y referring to the middle portion and |y|>0. What do we call the process of repeating y zero or more times before checking they still belong to the language L or not?
Generating
Pumping
Producing
None of the above
If we select a string w such that w ∈ L, and w=xyz, which of the following portions cannot be an empty string?
x
y
z
All of the above
While applying the pumping lemma over a language, we consider a string w that belongs to L and fragment it into __ parts.
2
5
3
6
Relate the following statement to any of the following options: “All sufficiently long words in a regular language can have a middle section of words repeated several times to produce a new word which also lies within the same language.”
Turing machine
Pumping lemma
Arden’s theorem
None of the above
The pumping lemma gives a necessary but not sufficient condition for the regularity of languages. True or false?
True
False
One can apply the pigeonhole principle in the following computer science algorithms
Hashing algorithm
Lossless compression algorithm
Hashing and lossless compression algorithms
None of the above
If n objects are distributed over m places, and n < m, then some of the places receive
At least 2 objects
At most 2 objects
No object
None of the above
Which of the following fields may violate the pigeonhole principle?
Discrete mathematics
Computer science
Quantum mechanics
None of the above
Which of the following one can relate to the given statement: “If n items are put into m containers, with n > m, then at least one container must contain more than one item.”
Pumping lemma
Pigeon hole principle
Count principle
None of the above
Which kind of proof is used for determining the regularity of a language?
Proof by contradiction
Direct proof
Proof by induction
None of the above
Which of the following is/are (an) example(s) of the pigeonhole principle?
Softball team
Sock picking
Hair counting
All of the above
