Theory of Computation Week 6 Nptel Assignment Answers
Are you looking for Theory of Computation Week 6 Nptel Assignment Answers? You’ve come to the right place! Access the latest and most accurate solutions for your Assignment 6 in the Theory of Computation course. Our detailed answers are designed to help you understand key concepts and excel in your studies.
Theory of Computation Week 6 Nptel Assignment Answers
Theory of Computation Week 6 Nptel Assignment Answers (July-Dec 2024)
1. Consider the following languages L1 = {anbnam ∣ n,m≥0} and L2 = {anbman ∣ n,m≥0}. Which of the following languages is DCFL?
A) L1¯¯¯¯¯¯ B) L1∩L2 C) L1∪L2 D) L1∩L2¯¯¯¯¯¯
Answer: D) L1∩L2¯¯¯¯¯¯
2. Which of the following languages is not necessarily context-free?
A) Complement of a DCFL B) Intersection of a DCFL and a regular language C) Union of two DCFLs D) Intersection of two DCFLs
Answer: A) Complement of a DCFL
3. Which of the following languages is necessarily deterministic context-free?
A) Complement of a DCFL B) Intersection of a DCFL and a regular language C) Union of two DCFLs D) Intersection of two DCFLs
Answer: D) Intersection of two DCFLs
4. Let L1 and L2 be two languages such that L1⊆L2. Consider the following statements: S1: If L1 is DCFL then L2 is also DCFL S2: If L2 is DCFL then L1 is also DCFL S3: Either both L1 and L2 are DCFL or neither L1 nor L2 is DCFL Which of the following is correct?
A) S1 is true B) S2 is true C) S3 is true D) None of S1, S2, S3 is true
5. Let L1 be a context-free language, L2 be a DCFL. Which of the following is not true?
A) L1¯¯¯¯¯¯∪L2 is necessarily context-free B) L1∪L2¯¯¯¯¯¯ is necessarily context-free C) L1⋅L2¯¯¯¯¯¯ is necessarily context-free D) L1∪L2 is necessarily context-free
Answer: B) L1∪L2¯¯¯¯¯¯ is necessarily context-free
6. Which of the following statements is not true about a deterministic Turing Machine?
A) Equivalent to a nondeterministic Turing Machine in terms of computability B) Can go to multiple configurations from a given configuration C) Can have multiple accept configurations D) Accepts a decidable language
Answer: B) Can go to multiple configurations from a given configuration
7. Which of the following is a deterministic context-free language?
A) {wwR∣w∈{0,1}∗ and wR is the reverse of w} B) {ww∣w∈{0,1}∗} C) {w∣w∈{0,1}∗ and w has equal number of 0’s and 1’s} D) {anbncm or anbmcn∣m,n are natural numbers}
Answer: A) {wwR∣w∈{0,1}∗ and wR is the reverse of w}
8. Which of the following statements is not true about a Turing Machine?
A) Can move across the work tape in both directions B) Can write on the work tape C) Has a fixed (independent of the input) number of states D) Has a fixed (independent of the input) number of configurations
Answer: D) Has a fixed (independent of the input) number of configurations
These are Theory of Computation Week 6 Nptel Assignment Answers
