Home / Study library / Theory of Computation / Quiz 2 · May 2026 Theory of Computation · Quiz 2 · May 2026
Theory of Computation · Quiz 2 · May 2026
← Course papers · Start practice / exam
Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.
0 / 16 published solutions
Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10 Q11 Q12 Q13 Q14 Q15 Q16 Q17 Question 2 MCQ · 3.0 marks Let
be recognized by a DFA
. A new DFA
is constructed from
by
interchanging the accepting and non-accepting states.
A student claims that
always recognizes
.
Which of the following conditions is essential for the claim to be valid?
6406537134807. Every state of
must be reachable from the start state.
6406537134808. must have exactly one accepting state.
6406537134809. The DFA must be complete (i.e., the transition function is defined for every
state-symbol pair).
6406537134810. must not contain cycles.
A published solution is not available for this question yet.
Report a correction for Q2
Question 3 MCQ · 3.0 marks Consider the language
A student proposes to prove that
is non-regular using the Pumping Lemma for regular
languages.
Which of the following best identifies the flaw in this approach?
6406537134817. The Pumping Lemma cannot be applied to languages containing two symbols.
6406537134818. The language is regular because only the total length modulo
needs to be
tracked, together with whether a
has already appeared.
6406537134819. The language is context-free but not regular because
and
are unbounded.
6406537134820. Pumping Lemma proofs require the selected string to contain equal numbers
of 0s and 1s.
A published solution is not available for this question yet.
Report a correction for Q3
Question 4 MCQ · 3.0 marks Consider the context-free grammar
.
Which of the following best describes
?
6406537134825. 6406537134826. 6406537134827. 6406537134828. A published solution is not available for this question yet.
Report a correction for Q4
Question 5 MCQ · 3.0 marks A PDA
recognizes a language
by final state. A new PDA
is obtained by declaring every non-
final state of
to be final and every final state to be non-final.
A student claims that
.
Which of the following best explains why the claim is incorrect in general?
6406537134834. PDAs cannot have more than one final state.
6406537134835. A string may have both accepting and rejecting computation paths in a
nondeterministic PDA.
6406537134836. Complementation changes the stack alphabet of a PDA.
6406537134837. A PDA cannot recognize an infinite language after final states are
interchanged.
A published solution is not available for this question yet.
Report a correction for Q5
Question 6 MCQ · 3.0 marks A Turing Machine
has the following high-level behavior on input
:
1. Scan right and mark the leftmost unmarked symbol.
2. Move to the right end of the input.
3. Scan left to locate the rightmost unmarked symbol.
4. Reject if the two selected symbols are different.
5. Mark the rightmost symbol and return to the left end.
6. Repeat until no unmarked symbols remain.
Which language is recognized by
?
6406537134844. 6406537134845. 6406537134846. 6406537134847. A published solution is not available for this question yet.
Report a correction for Q6
Question 7 NAT · 3.0 marks Consider the language
A DFA is constructed by independently tracking:
• the length of the input modulo
, and
• the parity of the number of 1s.
After removing unreachable states, how many states are present in the DFA?
A published solution is not available for this question yet.
Report a correction for Q7
Question 8 NAT · 3.0 marks Consider the regular expression
.
Let
denote the number of distinct strings of length exactly
generated by
.
What is the value of
?
A published solution is not available for this question yet.
Report a correction for Q8
Question 9 NAT · 3.0 marks Consider the context-free grammar
.
A variable is called useless if it does not participate in the derivation of any terminal string from
the start variable
.
How many useless variables are present in the grammar?
A published solution is not available for this question yet.
Report a correction for Q9
Question 10 NAT · 3.0 marks A PDA begins with stack symbol
.
While reading an input, it performs the following stack operations in order:
1. Replace
by
2. Replace
by
3. Replace
by
4. Replace
by
5. Replace
by
6. Replace
by
Assume the leftmost symbol is the top of the stack.
What is the height of the stack after all six operations, counting
?
A published solution is not available for this question yet.
Report a correction for Q10
Question 11 NAT · 3.0 marks A two-tape Turing Machine performs
computational steps.
A single-tape simulation represents the contents of both tapes on one tape. To simulate the
-th
step of the two-tape machine, the single-tape machine performs exactly
transitions.
If the two-tape machine performs exactly
steps, how many transitions are performed by the
single-tape simulation?
A published solution is not available for this question yet.
Report a correction for Q11
Question 12 MSQ · 3.0 marks Let
and
be arbitrary regular languages over the same alphabet
.
Define
.
Which of the following statements are necessarily TRUE?
6406537134812. is regular.
6406537134813. If
, then
.
6406537134814. can be recognized using a finite automaton.
6406537134815. If
, then
.
A published solution is not available for this question yet.
Report a correction for Q12
Question 13 MSQ · 3.0 marks Let
. Suppose there exist infinitely many strings
such that for every
, there exists a string
satisfying exactly one of
and
belongs to
.
Which of the following conclusions are valid?
6406537134821. is not regular.
6406537134822. No finite-state deterministic automaton can recognize
.
6406537134823. has infinitely many Nerode equivalence classes.
6406537134824. cannot be context-free.
A published solution is not available for this question yet.
Report a correction for Q13
Question 14 MSQ · 3.0 marks Let
be an arbitrary context-free language and let
be an arbitrary regular language over the
same alphabet
.
Which of the following languages are necessarily context-free?
6406537134830. 6406537134831. 6406537134832. 6406537134833. A published solution is not available for this question yet.
Report a correction for Q14
Question 15 MSQ · 3.0 marks Let
and
Which of the following statements are TRUE?
6406537134849. is Turing-recognizable.
6406537134850. is decidable.
6406537134851. is Turing-recognizable.
6406537134852. If
were decidable, every Turing-recognizable language would be
decidable.
6406537134853. The complement of
is Turing-recognizable.
A published solution is not available for this question yet.
Report a correction for Q15
Question 16 MSQ · 4.0 marks Consider the language
.
A student argues:
"L is context-free because the condition
can be checked by one PDA and the condition
can be checked by another PDA. Therefore, a PDA can check both conditions."
Which of the following statements correctly analyze the argument?
6406537134839. The language is
.
6406537134840. The student's argument incorrectly assumes that CFLs are closed under
intersection.
6406537134841. The language can be recognized by a Linear Bounded Automaton.
6406537134842. The language is context-free because each equality can independently be
checked using a stack.
6406537134843. The language is context-sensitive.
A published solution is not available for this question yet.
Report a correction for Q16
Question 17 MSQ · 4.0 marks For a Turing Machine
, define
Also define
Which of the following statements are TRUE?
6406537134854. Whether
is empty is a property of the language recognized by
.
6406537134855. Rice's Theorem can be used to conclude that
is undecidable.
6406537134856. is Turing-recognizable.
6406537134857. is Turing-recognizable because a Turing Machine can simulate
on every possible input.
6406537134858. If both
and
were Turing-recognizable, then
would be decidable.
A published solution is not available for this question yet.
Report a correction for Q17
