Theory of Computation · End Term · May 2026 · AN

Theory of Computation · End Term · May 2026 AN

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

Question 2 MCQ · 3.0 marks

Consider the DFA below over

.

Which of the following statements correctly describes the language accepted by the DFA?

6406537405849.

All strings containing exactly three

's

6406537405850.

All strings containing at least three

's

6406537405851.

All strings ending with

6406537405852.

All strings containing at least three consecutive

's

A published solution is not available for this question yet.

Report a correction for Q2

Question 3 MCQ · 3.0 marks

Consider the regular expression

Which of the following statements is **correct**?

6406537405858.

consists only of strings that begin with

6406537405859.

consists only of strings containing an even number of

's

6406537405860.

(the language of all binary strings)

6406537405861.

excludes the string

A published solution is not available for this question yet.

Report a correction for Q3

Question 4 MCQ · 3.0 marks

Let

and consider the language:

What is the index of the Myhill–Nerode equivalence relation

?

6406537405867.

3

6406537405868.

4

6406537405869.

5

6406537405870.

6

A published solution is not available for this question yet.

Report a correction for Q4

Question 5 MCQ · 3.0 marks

Consider the following grammar:

Using the CYK algorithm for the string

, which non-terminals occur in the table entry for the entire string?

6406537405879.

6406537405880.

6406537405881.

6406537405882.

A published solution is not available for this question yet.

Report a correction for Q5

Question 6 MCQ · 3.0 marks

Which of the following languages is context-free?

6406537405892.

6406537405893.

6406537405894.

6406537405895.

A published solution is not available for this question yet.

Report a correction for Q6

Question 7 MCQ · 3.0 marks

Suppose

Which of the following statements must hold?

6406537405914.

6406537405915.

6406537405916.

and

must be equivalent under mapping reduction

6406537405917.

If

is decidable, then

must be undecidable

A published solution is not available for this question yet.

Report a correction for Q7

Question 8 MSQ · 3.0 marks

Consider the following DFA.

Which of the following strings are accepted?

6406537405853.

0

6406537405854.

01

6406537405855.

110

6406537405856.

1011

6406537405857.

1110

A published solution is not available for this question yet.

Report a correction for Q8

Question 9 MSQ · 3.0 marks

Consider the grammar

Which of the following strings can be generated by the grammar?

6406537405871.

6406537405872.

6406537405873.

6406537405874.

A published solution is not available for this question yet.

Report a correction for Q9

Question 10 MSQ · 3.0 marks

Consider the grammar

Which of the following statements are correct?

6406537405875.

The grammar is in Chomsky Normal Form

6406537405876.

The grammar generates only strings of the form

6406537405877.

The grammar generates

6406537405878.

The grammar generates the empty string

A published solution is not available for this question yet.

Report a correction for Q10

Question 11 MSQ · 3.0 marks

Consider the language

A PDA is designed to recognize

by using the symbol

as a unique middle marker. In the standard stack-based PDA construction described above, which of the following operations are performed?

6406537405883.

Push each symbol of

before reading

6406537405884.

Change to a popping state after reading

6406537405885.

Match each symbol after

with the stack top

6406537405886.

Push all symbols after

before comparing them

6406537405887.

Accept when the input is exhausted and the stack is back at its bottom marker

A published solution is not available for this question yet.

Report a correction for Q11

Question 12 MSQ · 3.0 marks

A Pushdown Automaton (PDA) has the following transition:

Which of the following statements are correct?

6406537405888.

The transition consumes an input symbol

6406537405889.

The PDA can move to either

or

6406537405890.

One possible move removes

from the stack

6406537405891.

One possible move replaces

by

A published solution is not available for this question yet.

Report a correction for Q12

Question 13 MSQ · 3.0 marks

Let

Which of the following statements are correct?

6406537405909.

is a semantic property of the language recognized by

6406537405910.

is a non-trivial property

6406537405911.

Rice's Theorem implies that

is undecidable

6406537405912.

depends only on the number of states of

6406537405913.

is decidable because only one input,

, is checked

A published solution is not available for this question yet.

Report a correction for Q13

Question 14 NAT · 3.0 marks

Consider the following NFA over

:

**Transition Table:**

Using standard subset construction and considering only reachable subsets, how many states does the equivalent DFA have?

A published solution is not available for this question yet.

Report a correction for Q14

Question 15 NAT · 3.0 marks

A nondeterministic Turing Machine has at most

possible transitions from every configuration. Suppose the machine is explored using breadth-first search up to depth

, including the initial configuration. What is the maximum number of configurations explored?

A published solution is not available for this question yet.

Report a correction for Q15

Question 16 MCQ · 2.0 marks

Let

Which of the following statements are Incorrect?

6406537405863.

is regular

6406537405864.

A DFA can remember the first symbol using finitely many states

6406537405865.

requires an unbounded stack

6406537405866.

can be recognized by a regular expression

A published solution is not available for this question yet.

Report a correction for Q16

Question 17 MCQ · 2.0 marks

Consider the language

Which of the following statements correctly classifies

in the Chomsky hierarchy?

6406537405896.

is regular

6406537405897.

is context-free

6406537405898.

is context-sensitive but not context-free

6406537405899.

is not recursively enumerable

A published solution is not available for this question yet.

Report a correction for Q17

Question 19 MCQ · 2.0 marks

Let

Which of the following statements is **correct** regarding the language

?

6406537405905.

is recursive (decidable)

6406537405906.

is recursively enumerable but undecidable

6406537405907.

is not recursively enumerable

6406537405908.

is decidable because a Universal Turing Machine can simulate

on

A published solution is not available for this question yet.

Report a correction for Q19