Theory of Computation · End Term · Jan 2026 · FN

Theory of Computation · End Term · Jan 2026 FN

← 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 / 20 published solutions

Question 2 MSQ · 3.0 marks

Consider an

-NFA

with states

, start state

, and accepting state

. The transitions are: •

,

•

,

•

,

•

has no outgoing transitions Let

be the DFA obtained using subset construction. Which of the following statements is/are correct?

6406536959223.

The start state of

is

6406536959224.

The start state of

is

6406536959225.

The DFA accepts all binary strings that end with either

or

6406536959226.

The DFA accepts all strings containing both

and

6406536959227.

Every accepting state of

must contain

A published solution is not available for this question yet.

Report a correction for Q2

Question 3 MCQ · 3.0 marks

Consider the DFA below. start state =

, and accepting state =

.

What language does the given DFA accept?

6406536959228.

All strings of length

6406536959229.

All strings with equal number of

's and

's

6406536959230.

All strings consisting only of

's or only of

's

6406536959231.

All strings that do not contain the substring

A published solution is not available for this question yet.

Report a correction for Q3

Question 4 MCQ · 3.0 marks

Consider a PDA with the following behavior: • For every

, it pushes one symbol

onto the stack. • For every

, it pops one

from the stack. • After the stack becomes

, it can read any number of

'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?

6406536959245.

6406536959246.

6406536959247.

6406536959248.

A published solution is not available for this question yet.

Report a correction for Q4

Question 5 MCQ · 3.0 marks

Consider a 2-tape Turing Machine with the transition:

Initially: • Head

is at position 3 • Head

is at position 2 After one transition, where will the heads be?

6406536959259.

6406536959260.

6406536959261.

6406536959262.

A published solution is not available for this question yet.

Report a correction for Q5

Question 6 MCQ · 3.0 marks

Consider the PCP instance with tiles:

Apply the sequence

. What are the unmatched suffixes?

6406536959273.

top:

, bottom:

6406536959274.

top:

, bottom:

6406536959275.

top:

, bottom:

6406536959276.

No mismatch

A published solution is not available for this question yet.

Report a correction for Q6

Question 7 MSQ · 2.0 marks

Consider the grammar

. Which of the following statements is/are correct?

6406536959232.

The language generated by

is

6406536959233.

Every string generated by

ends with the substring

6406536959234.

The grammar generates infinitely many strings

6406536959235.

The grammar generates all strings with equal number of

's and

's

6406536959236.

The empty string

is in the language

A published solution is not available for this question yet.

Report a correction for Q7

Question 8 MSQ · 2.0 marks

Let:

Which of the following languages is/are necessarily context-free?

6406536959241.

6406536959242.

6406536959243.

6406536959244.

A published solution is not available for this question yet.

Report a correction for Q8

Question 9 MSQ · 2.0 marks

Consider the PDA transition:

Which of the following statements is/are correct?

6406536959249.

The input symbol

is consumed

6406536959250.

The stack top

is replaced by

6406536959251.

The symbol

becomes the new top of the stack

6406536959252.

The stack size decreases by 1

6406536959253.

The PDA remains in state

A published solution is not available for this question yet.

Report a correction for Q9

Question 11 MSQ · 2.0 marks

Which of the following statements about mapping reductions are correct?

6406536959281.

If

and

is decidable, then

is decidable

6406536959282.

If

and

is undecidable, then

is undecidable

6406536959283.

If

, then

is harder than

6406536959284.

If

and

, then

6406536959285.

If

, then

and

are equivalent

A published solution is not available for this question yet.

Report a correction for Q11

Question 12 NAT · 3.0 marks

Consider a DFA

. Let

and

denote the sets of strings that take

from state

and

to an accepting state, respectively.

How many strings of length exactly

belong to

?

A published solution is not available for this question yet.

Report a correction for Q12

Question 13 NAT · 3.0 marks

Let

What is the index of the Nerode equivalence relation

?

A published solution is not available for this question yet.

Report a correction for Q13

Question 14 NAT · 3.0 marks

Consider the grammar:

How many distinct parse trees exist for the string:

A published solution is not available for this question yet.

Report a correction for Q14

Question 15 NAT · 3.0 marks

Let a string

have length

. In the CYK algorithm, how many entries

are there such that

?

A published solution is not available for this question yet.

Report a correction for Q15

Question 17 NAT · 2.0 marks

Consider the language

What is the minimum number of states required in a DFA that recognizes

?

A published solution is not available for this question yet.

Report a correction for Q17

Question 18 MCQ · 2.0 marks

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

6406536959254.

6406536959255.

6406536959256.

6406536959257.

A published solution is not available for this question yet.

Report a correction for Q18

Question 19 MCQ · 2.0 marks

An enumerator prints strings of a language

in the following order:

A machine

recognizes

by: • Simulating the enumerator step-by-step • Accepting when the input string

is printed If

and the enumerator prints one string every 3 steps, when will

accept?

6406536959269.

5

6406536959270.

10

6406536959271.

15

6406536959272.

May never accept

A published solution is not available for this question yet.

Report a correction for Q19

Question 20 MCQ · 2.0 marks

Let

and

be decision problems such that

and

is undecidable.Which of the following must be true?

6406536959277.

is decidable

6406536959278.

is undecidable

6406536959279.

is decidable

6406536959280.

A published solution is not available for this question yet.

Report a correction for Q20

Question 21 MCQ · 2.0 marks

If

and

is known to be recursively enumerable but not decidable, what can be concluded about

?

6406536959286.

must be undecidable

6406536959287.

must be recursively enumerable

6406536959288.

must not be recursively enumerable

6406536959289.

No definite conclusion can be drawn

A published solution is not available for this question yet.

Report a correction for Q21