cs3021_2026T2_Q2_NA.pdf

Theory of Computation · Quiz 2 · May 2026

Questions and published explanations below are available without starting a test. Some questions may not have a published solution yet.

Question 2 MCQ · 3.0 marks

Let [[IMAGE:b064f9a86b8421eb_2_2]] be recognized by a DFA [[IMAGE:b064f9a86b8421eb_2_3]] . A new DFA [[IMAGE:b064f9a86b8421eb_2_4]] is constructed from [[IMAGE:b064f9a86b8421eb_2_5]] by interchanging the accepting and non-accepting states. A student claims that [[IMAGE:b064f9a86b8421eb_2_6]] always recognizes [[IMAGE:b064f9a86b8421eb_2_7]] . Which of the following conditions is essential for the claim to be valid?

Every state of [[IMAGE:b064f9a86b8421eb_2_8]] must be reachable from the start state.
[[IMAGE:b064f9a86b8421eb_2_9]] must have exactly one accepting state.
The DFA must be complete (i.e., the transition function is defined for every state-symbol pair).
[[IMAGE:b064f9a86b8421eb_2_10]] must not contain cycles.

A published solution is not available for this question yet.

Question 3 MCQ · 3.0 marks

Consider the language [[IMAGE:b064f9a86b8421eb_2_11]] A student proposes to prove that [[IMAGE:b064f9a86b8421eb_2_12]] is non-regular using the Pumping Lemma for regular languages. Which of the following best identifies the flaw in this approach?

The Pumping Lemma cannot be applied to languages containing two symbols.
The language is regular because only the total length modulo [[IMAGE:b064f9a86b8421eb_3_13]] needs to be tracked, together with whether a [[IMAGE:b064f9a86b8421eb_3_14]] has already appeared.
The language is context-free but not regular because [[IMAGE:b064f9a86b8421eb_3_15]] and [[IMAGE:b064f9a86b8421eb_3_16]] are unbounded.
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.

Question 4 MCQ · 3.0 marks

Consider the context-free grammar [[IMAGE:b064f9a86b8421eb_3_17]] . Which of the following best describes [[IMAGE:b064f9a86b8421eb_3_18]] ?

[[IMAGE:b064f9a86b8421eb_3_19]]
[[IMAGE:b064f9a86b8421eb_3_20]]
[[IMAGE:b064f9a86b8421eb_3_21]]
[[IMAGE:b064f9a86b8421eb_3_22]]

A published solution is not available for this question yet.

Question 5 MCQ · 3.0 marks

A PDA [[IMAGE:b064f9a86b8421eb_3_23]] recognizes a language [[IMAGE:b064f9a86b8421eb_3_24]] by final state. A new PDA [[IMAGE:b064f9a86b8421eb_3_25]] is obtained by declaring every non- final state of [[IMAGE:b064f9a86b8421eb_3_26]] to be final and every final state to be non-final. A student claims that [[IMAGE:b064f9a86b8421eb_4_27]] . Which of the following best explains why the claim is incorrect in general?

PDAs cannot have more than one final state.
A string may have both accepting and rejecting computation paths in a nondeterministic PDA.
Complementation changes the stack alphabet of a PDA.
A PDA cannot recognize an infinite language after final states are interchanged.

A published solution is not available for this question yet.

Question 6 MCQ · 3.0 marks

A Turing Machine [[IMAGE:b064f9a86b8421eb_4_28]] has the following high-level behavior on input [[IMAGE:b064f9a86b8421eb_4_29]] : 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 [[IMAGE:b064f9a86b8421eb_4_30]] ?

[[IMAGE:b064f9a86b8421eb_4_31]]
[[IMAGE:b064f9a86b8421eb_4_32]]
[[IMAGE:b064f9a86b8421eb_4_33]]
[[IMAGE:b064f9a86b8421eb_4_34]]

A published solution is not available for this question yet.

Question 7 NAT · 3.0 marks

Consider the language [[IMAGE:b064f9a86b8421eb_5_35]] A DFA is constructed by independently tracking: • the length of the input modulo [[IMAGE:b064f9a86b8421eb_5_36]] , 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.

Question 8 NAT · 3.0 marks

Consider the regular expression [[IMAGE:b064f9a86b8421eb_5_37]] . Let [[IMAGE:b064f9a86b8421eb_5_38]] denote the number of distinct strings of length exactly [[IMAGE:b064f9a86b8421eb_5_39]] generated by [[IMAGE:b064f9a86b8421eb_5_40]] . What is the value of [[IMAGE:b064f9a86b8421eb_5_41]] ?

A published solution is not available for this question yet.

Question 9 NAT · 3.0 marks

Consider the context-free grammar [[IMAGE:b064f9a86b8421eb_6_42]] [[IMAGE:b064f9a86b8421eb_6_43]] [[IMAGE:b064f9a86b8421eb_6_44]] [[IMAGE:b064f9a86b8421eb_6_45]] [[IMAGE:b064f9a86b8421eb_6_46]] [[IMAGE:b064f9a86b8421eb_6_47]] . A variable is called useless if it does not participate in the derivation of any terminal string from the start variable [[IMAGE:b064f9a86b8421eb_6_48]] . How many useless variables are present in the grammar?

A published solution is not available for this question yet.

Question 10 NAT · 3.0 marks

A PDA begins with stack symbol [[IMAGE:b064f9a86b8421eb_6_49]] . While reading an input, it performs the following stack operations in order: 1. Replace [[IMAGE:b064f9a86b8421eb_6_50]] by [[IMAGE:b064f9a86b8421eb_6_51]] 2. Replace [[IMAGE:b064f9a86b8421eb_6_52]] by [[IMAGE:b064f9a86b8421eb_6_53]] 3. Replace [[IMAGE:b064f9a86b8421eb_6_54]] by [[IMAGE:b064f9a86b8421eb_6_55]] 4. Replace [[IMAGE:b064f9a86b8421eb_6_56]] by [[IMAGE:b064f9a86b8421eb_6_57]] 5. Replace [[IMAGE:b064f9a86b8421eb_6_58]] by [[IMAGE:b064f9a86b8421eb_6_59]] 6. Replace [[IMAGE:b064f9a86b8421eb_6_60]] by [[IMAGE:b064f9a86b8421eb_6_61]] Assume the leftmost symbol is the top of the stack. What is the height of the stack after all six operations, counting [[IMAGE:b064f9a86b8421eb_7_62]] ?

A published solution is not available for this question yet.

Question 11 NAT · 3.0 marks

A two-tape Turing Machine performs [[IMAGE:b064f9a86b8421eb_7_63]] computational steps. A single-tape simulation represents the contents of both tapes on one tape. To simulate the [[IMAGE:b064f9a86b8421eb_7_64]] -th step of the two-tape machine, the single-tape machine performs exactly [[IMAGE:b064f9a86b8421eb_7_65]] transitions. If the two-tape machine performs exactly [[IMAGE:b064f9a86b8421eb_7_66]] steps, how many transitions are performed by the single-tape simulation?

A published solution is not available for this question yet.

Question 12 MSQ · 3.0 marks

Let [[IMAGE:b064f9a86b8421eb_8_67]] and [[IMAGE:b064f9a86b8421eb_8_68]] be arbitrary regular languages over the same alphabet [[IMAGE:b064f9a86b8421eb_8_69]] . Define [[IMAGE:b064f9a86b8421eb_8_70]] . Which of the following statements are necessarily TRUE?

[[IMAGE:b064f9a86b8421eb_8_71]] is regular.
If [[IMAGE:b064f9a86b8421eb_8_72]] , then [[IMAGE:b064f9a86b8421eb_8_73]] .
[[IMAGE:b064f9a86b8421eb_8_74]] can be recognized using a finite automaton.
If [[IMAGE:b064f9a86b8421eb_8_75]] , then [[IMAGE:b064f9a86b8421eb_8_76]] .

A published solution is not available for this question yet.

Question 13 MSQ · 3.0 marks

Let [[IMAGE:b064f9a86b8421eb_8_77]] . Suppose there exist infinitely many strings [[IMAGE:b064f9a86b8421eb_8_78]] such that for every [[IMAGE:b064f9a86b8421eb_8_79]] , there exists a string [[IMAGE:b064f9a86b8421eb_8_80]] satisfying exactly one of [[IMAGE:b064f9a86b8421eb_8_81]] and [[IMAGE:b064f9a86b8421eb_8_82]] belongs to [[IMAGE:b064f9a86b8421eb_8_83]] . Which of the following conclusions are valid?

[[IMAGE:b064f9a86b8421eb_8_84]] is not regular.
No finite-state deterministic automaton can recognize [[IMAGE:b064f9a86b8421eb_8_85]] .
[[IMAGE:b064f9a86b8421eb_8_86]] has infinitely many Nerode equivalence classes.
[[IMAGE:b064f9a86b8421eb_8_87]] cannot be context-free.

A published solution is not available for this question yet.

Question 14 MSQ · 3.0 marks

Let [[IMAGE:b064f9a86b8421eb_9_88]] be an arbitrary context-free language and let [[IMAGE:b064f9a86b8421eb_9_89]] be an arbitrary regular language over the same alphabet [[IMAGE:b064f9a86b8421eb_9_90]] . Which of the following languages are necessarily context-free?

[[IMAGE:b064f9a86b8421eb_9_91]]
[[IMAGE:b064f9a86b8421eb_9_92]]
[[IMAGE:b064f9a86b8421eb_9_93]]
[[IMAGE:b064f9a86b8421eb_9_94]]

A published solution is not available for this question yet.

Question 15 MSQ · 3.0 marks

Let [[IMAGE:b064f9a86b8421eb_9_95]] and [[IMAGE:b064f9a86b8421eb_9_96]] Which of the following statements are TRUE?

[[IMAGE:b064f9a86b8421eb_9_97]] is Turing-recognizable.
[[IMAGE:b064f9a86b8421eb_9_98]] is decidable.
[[IMAGE:b064f9a86b8421eb_9_99]] is Turing-recognizable.
If [[IMAGE:b064f9a86b8421eb_9_100]] were decidable, every Turing-recognizable language would be decidable.
The complement of [[IMAGE:b064f9a86b8421eb_10_101]] is Turing-recognizable.

A published solution is not available for this question yet.

Question 16 MSQ · 4.0 marks

Consider the language [[IMAGE:b064f9a86b8421eb_10_102]] . A student argues: "L is context-free because the condition [[IMAGE:b064f9a86b8421eb_10_103]] can be checked by one PDA and the condition [[IMAGE:b064f9a86b8421eb_10_104]] can be checked by another PDA. Therefore, a PDA can check both conditions." Which of the following statements correctly analyze the argument?

The language is [[IMAGE:b064f9a86b8421eb_10_105]] .
The student's argument incorrectly assumes that CFLs are closed under intersection.
The language can be recognized by a Linear Bounded Automaton.
The language is context-free because each equality can independently be checked using a stack.
The language is context-sensitive.

A published solution is not available for this question yet.

Question 17 MSQ · 4.0 marks

For a Turing Machine [[IMAGE:b064f9a86b8421eb_10_106]] , define [[IMAGE:b064f9a86b8421eb_10_107]] Also define [[IMAGE:b064f9a86b8421eb_10_108]] Which of the following statements are TRUE?

Whether [[IMAGE:b064f9a86b8421eb_11_109]] is empty is a property of the language recognized by [[IMAGE:b064f9a86b8421eb_11_110]] .
Rice's Theorem can be used to conclude that [[IMAGE:b064f9a86b8421eb_11_111]] is undecidable.
[[IMAGE:b064f9a86b8421eb_11_112]] is Turing-recognizable.
[[IMAGE:b064f9a86b8421eb_11_113]] is Turing-recognizable because a Turing Machine can simulate [[IMAGE:b064f9a86b8421eb_11_114]] on every possible input.
If both [[IMAGE:b064f9a86b8421eb_11_115]] and [[IMAGE:b064f9a86b8421eb_11_116]] were Turing-recognizable, then [[IMAGE:b064f9a86b8421eb_11_117]] would be decidable.

A published solution is not available for this question yet.