Theory of Computation | Week 1
Session: JULY-DEC 2024
Course Name: Theory of Computation
Course Link: Click Here
For answers or latest updates join our telegram channel: Click here to join
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
Answer: 2n
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
Answer:3
For answers or latest updates join our telegram channel: Click here to join
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}
Answer: {q1}
Q4.Which of the following strings is accepted by the DFA below?
01011101
00111100
10100011
11000010
Answer:11000010
For answers or latest updates join our telegram channel: Click here to join
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
Answer: L is regular
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}
For answers or latest updates join our telegram channel: Click here to join
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
Answer: 2
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}
For answers or latest updates join our telegram channel: Click here to join
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
Answer: One
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.
For answers or latest updates join our telegram channel: Click here to join
These are Theory of Computation Week 1 Assignment 1 Nptel Answers
More Weeks of Theory of Computation: Click here
More Nptel Courses: https://progiez.com/nptel-assignment-answers
