# Theory of Computation | Week 1

Session: JULY-DEC 2024

Course Name: Theory of Computation

#### These are Theory of Computation Week 1 Assignment 1 Nptel Answers

Q1. Any NFA having n states can be converted to a DFA having at most (select the smallest possible value)

2n

3n

2n

n2

Q2. Consider the language L={w∣the number of 1’s in w is divisible by 3} over the binary alphabet {0,1}.What is the minimum number of states required for a DFA that accepts L
?
1
2
3
4

These are Theory of Computation Week 1 Assignment 1 Nptel Answers

Q3. What is the ϵ -closure of state q1 in the following NFA?
{q0,q1,q2}

{q0,q1,q2,q3}

{q0,q1}

{q1}

Q4.Which of the following strings is accepted by the DFA below?

01011101
00111100
10100011
11000010

These are Theory of Computation Week 1 Assignment 1 Nptel Answers

Q5. Let L1 and L2 be two regular languages. What can we say about the language L {w1w2∣w1∈L1,w2∈L2} ?

L may or may not be regular

L is regular

L is not regular

L is accepted by some NFA but there is no DFA that can accept L

Q6. What is the language accepted by the following NFA?

{w∈{0,1}∗∣w ends with 0 and begins with 1}

{w∈{0,1}∗∣w begins with 0 and ends with 1}

{w∈{0,1}∗∣w ends with 0 or begins with 1}

{w∈{0,1}∗∣w begins with 0 or ends with 1}

Answer:{w∈{0,1}∗∣w ends with 0 and begins with 1}

These are Theory of Computation Week 1 Assignment 1 Nptel Answers

Q7. Consider the language
L={w∈{0,1}∗∣w begins with 00}

How many states will the minimal DFA for L
have?
2
3
4
5

Q8. Consider the following DFA.

{w∈{0,1}∗∣w has exactly one 1}

{w∈{0,1}∗∣w ends with a 1}

{w∈{0,1}∗∣w begins with a 1}

{w∈{0,1}∗∣w consists of only 1’s}

Answer: {w∈{0,1}∗∣w has exactly one 1}

These are Theory of Computation Week 1 Assignment 1 Nptel Answers

Q9. The block of code displayed here is meant for the ball, how many loops are there in total?
One
Two
Three
Four

Q10. The block of code displayed here is meant for the ball, if the value beside repeat would have been 1 instead of 2, Select all the statements that explain the situation.
The Ball would not have returned to Cat.
Removing the loop from the code would have made no difference in the result.
The Ball would not have left its original position.
The code would throw an error

Answer: The Ball would not have returned to Cat
Removing the loop from the code would have made no difference in the result.