cs3021_2026T1_ET_FN.pdf

Theory of Computation · End Term · Jan 2026 FN

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

Question 2 MSQ · 3.0 marks

Consider an [[IMAGE:2b52ce2473ded384_2_2]] -NFA [[IMAGE:2b52ce2473ded384_2_3]] with states [[IMAGE:2b52ce2473ded384_2_4]] , start state [[IMAGE:2b52ce2473ded384_2_5]] , and accepting state [[IMAGE:2b52ce2473ded384_2_6]] . The transitions are: • [[IMAGE:2b52ce2473ded384_2_7]] , [[IMAGE:2b52ce2473ded384_2_8]] • [[IMAGE:2b52ce2473ded384_2_9]] , [[IMAGE:2b52ce2473ded384_2_10]] • [[IMAGE:2b52ce2473ded384_2_11]] , [[IMAGE:2b52ce2473ded384_2_12]] • [[IMAGE:2b52ce2473ded384_2_13]] has no outgoing transitions Let [[IMAGE:2b52ce2473ded384_2_14]] be the DFA obtained using subset construction. Which of the following statements is/are correct?

The start state of [[IMAGE:2b52ce2473ded384_2_15]] is [[IMAGE:2b52ce2473ded384_2_16]]
The start state of [[IMAGE:2b52ce2473ded384_2_17]] is [[IMAGE:2b52ce2473ded384_2_18]]
The DFA accepts all binary strings that end with either [[IMAGE:2b52ce2473ded384_2_19]] or [[IMAGE:2b52ce2473ded384_2_20]]
The DFA accepts all strings containing both [[IMAGE:2b52ce2473ded384_3_21]] and [[IMAGE:2b52ce2473ded384_3_22]]
Every accepting state of [[IMAGE:2b52ce2473ded384_3_23]] must contain [[IMAGE:2b52ce2473ded384_3_24]]

A published solution is not available for this question yet.

Question 3 MCQ · 3.0 marks

Consider the DFA below. start state = [[IMAGE:2b52ce2473ded384_3_25]] , and accepting state = [[IMAGE:2b52ce2473ded384_3_26]] . [[IMAGE:2b52ce2473ded384_3_27]] What language does the given DFA accept?

All strings of length [[IMAGE:2b52ce2473ded384_3_28]]
All strings with equal number of [[IMAGE:2b52ce2473ded384_3_29]] 's and [[IMAGE:2b52ce2473ded384_3_30]] 's
All strings consisting only of [[IMAGE:2b52ce2473ded384_3_31]] 's or only of [[IMAGE:2b52ce2473ded384_3_32]] 's
All strings that do not contain the substring [[IMAGE:2b52ce2473ded384_3_33]]

A published solution is not available for this question yet.

Question 4 MCQ · 3.0 marks

Consider a PDA with the following behavior: • For every [[IMAGE:2b52ce2473ded384_4_34]] , it pushes one symbol [[IMAGE:2b52ce2473ded384_4_35]] onto the stack. • For every [[IMAGE:2b52ce2473ded384_4_36]] , it pops one [[IMAGE:2b52ce2473ded384_4_37]] from the stack. • After the stack becomes [[IMAGE:2b52ce2473ded384_4_38]] , it can read any number of [[IMAGE:2b52ce2473ded384_4_39]] 's without changing the stack. • The PDA accepts by final state after all input is consumed. Which of the following languages is recognized by this PDA?

[[IMAGE:2b52ce2473ded384_4_40]]
[[IMAGE:2b52ce2473ded384_4_41]]
[[IMAGE:2b52ce2473ded384_4_42]]
[[IMAGE:2b52ce2473ded384_4_43]]

A published solution is not available for this question yet.

Question 5 MCQ · 3.0 marks

Consider a 2-tape Turing Machine with the transition: [[IMAGE:2b52ce2473ded384_4_44]] Initially: • Head [[IMAGE:2b52ce2473ded384_4_45]] is at position 3 • Head [[IMAGE:2b52ce2473ded384_5_46]] is at position 2 After one transition, where will the heads be?

[[IMAGE:2b52ce2473ded384_5_47]]
[[IMAGE:2b52ce2473ded384_5_48]]
[[IMAGE:2b52ce2473ded384_5_49]]
[[IMAGE:2b52ce2473ded384_5_50]]

A published solution is not available for this question yet.

Question 6 MCQ · 3.0 marks

Consider the PCP instance with tiles: [[IMAGE:2b52ce2473ded384_5_51]] Apply the sequence [[IMAGE:2b52ce2473ded384_5_52]] . What are the unmatched suffixes?

top: [[IMAGE:2b52ce2473ded384_5_53]] , bottom: [[IMAGE:2b52ce2473ded384_5_54]]
top: [[IMAGE:2b52ce2473ded384_5_55]] , bottom: [[IMAGE:2b52ce2473ded384_5_56]]
top: [[IMAGE:2b52ce2473ded384_5_57]] , bottom: [[IMAGE:2b52ce2473ded384_5_58]]
No mismatch

A published solution is not available for this question yet.

Question 7 MSQ · 2.0 marks

Consider the grammar [[IMAGE:2b52ce2473ded384_6_59]] . Which of the following statements is/are correct?

The language generated by [[IMAGE:2b52ce2473ded384_6_60]] is [[IMAGE:2b52ce2473ded384_6_61]]
Every string generated by [[IMAGE:2b52ce2473ded384_6_62]] ends with the substring [[IMAGE:2b52ce2473ded384_6_63]]
The grammar generates infinitely many strings
The grammar generates all strings with equal number of [[IMAGE:2b52ce2473ded384_6_64]] 's and [[IMAGE:2b52ce2473ded384_6_65]] 's
The empty string [[IMAGE:2b52ce2473ded384_6_66]] is in the language

A published solution is not available for this question yet.

Question 8 MSQ · 2.0 marks

Let: [[IMAGE:2b52ce2473ded384_6_67]] Which of the following languages is/are necessarily context-free?

[[IMAGE:2b52ce2473ded384_6_68]]
[[IMAGE:2b52ce2473ded384_6_69]]
[[IMAGE:2b52ce2473ded384_6_70]]
[[IMAGE:2b52ce2473ded384_6_71]]

A published solution is not available for this question yet.

Question 9 MSQ · 2.0 marks

Consider the PDA transition: [[IMAGE:2b52ce2473ded384_7_72]] Which of the following statements is/are correct?

The input symbol [[IMAGE:2b52ce2473ded384_7_73]] is consumed
The stack top [[IMAGE:2b52ce2473ded384_7_74]] is replaced by [[IMAGE:2b52ce2473ded384_7_75]]
The symbol [[IMAGE:2b52ce2473ded384_7_76]] becomes the new top of the stack
The stack size decreases by 1
The PDA remains in state [[IMAGE:2b52ce2473ded384_7_77]]

A published solution is not available for this question yet.

Question 10 MSQ · 2.0 marks

Which of the following statements is/are correct?

Every recursive language is recursively enumerable
There exists a recursively enumerable language that is not recursive
Every recursively enumerable language is recursive
A Turing machine recognizing an RE language may loop on some inputs
A decider may loop on some inputs

A published solution is not available for this question yet.

Question 11 MSQ · 2.0 marks

Which of the following statements about mapping reductions are correct?

If [[IMAGE:2b52ce2473ded384_7_78]] and [[IMAGE:2b52ce2473ded384_7_79]] is decidable, then [[IMAGE:2b52ce2473ded384_7_80]] is decidable
If [[IMAGE:2b52ce2473ded384_7_81]] and [[IMAGE:2b52ce2473ded384_7_82]] is undecidable, then [[IMAGE:2b52ce2473ded384_7_83]] is undecidable
If [[IMAGE:2b52ce2473ded384_7_84]] , then [[IMAGE:2b52ce2473ded384_7_85]] is harder than [[IMAGE:2b52ce2473ded384_7_86]]
If [[IMAGE:2b52ce2473ded384_8_87]] and [[IMAGE:2b52ce2473ded384_8_88]] , then [[IMAGE:2b52ce2473ded384_8_89]]
If [[IMAGE:2b52ce2473ded384_8_90]] , then [[IMAGE:2b52ce2473ded384_8_91]] and [[IMAGE:2b52ce2473ded384_8_92]] are equivalent

A published solution is not available for this question yet.

Question 12 NAT · 3.0 marks

Consider a DFA [[IMAGE:2b52ce2473ded384_8_93]] . Let [[IMAGE:2b52ce2473ded384_8_94]] and [[IMAGE:2b52ce2473ded384_8_95]] denote the sets of strings that take [[IMAGE:2b52ce2473ded384_8_96]] from state [[IMAGE:2b52ce2473ded384_8_97]] and [[IMAGE:2b52ce2473ded384_8_98]] to an accepting state, respectively. [[IMAGE:2b52ce2473ded384_8_99]] [[IMAGE:2b52ce2473ded384_8_100]] How many strings of length exactly [[IMAGE:2b52ce2473ded384_8_101]] belong to [[IMAGE:2b52ce2473ded384_8_102]] ?

A published solution is not available for this question yet.

Question 13 NAT · 3.0 marks

Let [[IMAGE:2b52ce2473ded384_8_103]] What is the index of the Nerode equivalence relation [[IMAGE:2b52ce2473ded384_8_104]] ?

A published solution is not available for this question yet.

Question 14 NAT · 3.0 marks

Consider the grammar: [[IMAGE:2b52ce2473ded384_9_105]] How many distinct parse trees exist for the string: [[IMAGE:2b52ce2473ded384_9_106]]

A published solution is not available for this question yet.

Question 15 NAT · 3.0 marks

Let a string [[IMAGE:2b52ce2473ded384_9_107]] have length [[IMAGE:2b52ce2473ded384_9_108]] . In the CYK algorithm, how many entries [[IMAGE:2b52ce2473ded384_9_109]] are there such that [[IMAGE:2b52ce2473ded384_9_110]] ?

A published solution is not available for this question yet.

Question 16 NAT · 3.0 marks

A non-deterministic Turing Machine has a branching factor 3. How many total configurations are explored by BFS up to level 4 (including level 0)?

A published solution is not available for this question yet.

Question 17 NAT · 2.0 marks

Consider the language [[IMAGE:2b52ce2473ded384_10_111]] What is the minimum number of states required in a DFA that recognizes [[IMAGE:2b52ce2473ded384_10_112]] ?

A published solution is not available for this question yet.

Question 18 MCQ · 2.0 marks

Which of the following languages is context-sensitive but **not** context-free?

[[IMAGE:2b52ce2473ded384_11_113]]
[[IMAGE:2b52ce2473ded384_11_114]]
[[IMAGE:2b52ce2473ded384_11_115]]
[[IMAGE:2b52ce2473ded384_11_116]]

A published solution is not available for this question yet.

Question 19 MCQ · 2.0 marks

An enumerator prints strings of a language [[IMAGE:2b52ce2473ded384_11_117]] in the following order: [[IMAGE:2b52ce2473ded384_11_118]] A machine [[IMAGE:2b52ce2473ded384_11_119]] recognizes [[IMAGE:2b52ce2473ded384_11_120]] by: • Simulating the enumerator step-by-step • Accepting when the input string [[IMAGE:2b52ce2473ded384_11_121]] is printed If [[IMAGE:2b52ce2473ded384_11_122]] and the enumerator prints one string every 3 steps, when will [[IMAGE:2b52ce2473ded384_11_123]] accept?

5
10
15
May never accept

A published solution is not available for this question yet.

Question 20 MCQ · 2.0 marks

Let [[IMAGE:2b52ce2473ded384_11_124]] and [[IMAGE:2b52ce2473ded384_11_125]] be decision problems such that [[IMAGE:2b52ce2473ded384_11_126]] and [[IMAGE:2b52ce2473ded384_11_127]] is undecidable.Which of the following must be true?

[[IMAGE:2b52ce2473ded384_12_128]] is decidable
[[IMAGE:2b52ce2473ded384_12_129]] is undecidable
[[IMAGE:2b52ce2473ded384_12_130]] is decidable
[[IMAGE:2b52ce2473ded384_12_131]]

A published solution is not available for this question yet.

Question 21 MCQ · 2.0 marks

If [[IMAGE:2b52ce2473ded384_12_132]] and [[IMAGE:2b52ce2473ded384_12_133]] is known to be recursively enumerable but not decidable, what can be concluded about [[IMAGE:2b52ce2473ded384_12_134]] ?

[[IMAGE:2b52ce2473ded384_12_135]] must be undecidable
[[IMAGE:2b52ce2473ded384_12_136]] must be recursively enumerable
[[IMAGE:2b52ce2473ded384_12_137]] must not be recursively enumerable
No definite conclusion can be drawn

A published solution is not available for this question yet.