Theory of Computation Week 4 Nptel Assignment Answers
Are you looking for Theory of Computation Week 4 Nptel Assignment Answers? You’ve come to the right place! Access the latest and most accurate solutions for your Assignment 4 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 4 Nptel Assignment Answers
Theory of Computation Week 4 Nptel Assignment Answers (July-Dec 2024)
1. Consider the following context-free grammar:
S → S0S1 ∣ S1S0 ∣ ϵ
Which of the following is the language generated by this grammar? A) Set of all palindromes B) Set of all even numbers C) Set of all strings having either only 0’s or only 1’s D) Set of all strings having equal number of 0’s and 1’s
Answer: D) Set of all strings having equal number of 0’s and 1’s
2. Consider the following grammar:
S ⟶ PQ ∣ ϵ P ⟶ PP ∣ ϵ Q ⟶ QQ ∣ ϵ
Which of the following regular expressions generates the same language as the given grammar? A) 0∗1∗ B) 0∗ + 1∗ C) (0 + 1)∗ D) 00∗11∗
Answer: A) 0∗1∗
3. Consider the following grammar:
S ⟶ 0AB ∣ 1BA ∣ ϵ A ⟶ 0A0 ∣ 1A1 ∣ ϵ B ⟶ 0B1 ∣ 1B0 ∣ ϵ
Which of the following strings does not belong to the language generated by this grammar? A) 0011010 B) 0101001 C) 1101000 D) 1011001
Answer: B) 0101001
4. Consider the following DFA:
Which of the following context-free grammars generate the same language as the given DFA? A) S ⟶ aA ∣ bB A ⟶ aA ∣ bA′ B ⟶ bB ∣ aB′ A′ ⟶ aA′ ∣ bC B′ ⟶ bB′ ∣ aC C ⟶ aC ∣ bC ∣ ϵ
B) S ⟶ aA ∣ bB A ⟶ bA ∣ aA′ B ⟶ aB ∣ bB′ A′ ⟶ aA′ ∣ bC B′ ⟶ bB′ ∣ aC C ⟶ aC ∣ bC ∣ ϵ
C) S ⟶ aA ∣ bB A ⟶ aA ∣ bA′ B ⟶ bB ∣ aB′ A′ ⟶ aA′ ∣ bC B′ ⟶ bB′ ∣ aC C ⟶ aC ∣ bC ∣ a ∣ b
D) S ⟶ aA ∣ bB A ⟶ aA ∣ bA′ B ⟶ bB ∣ aB′ A′ ⟶ bA′ ∣ aC B′ ⟶ aB′ ∣ bC C ⟶ aC ∣ bC ∣ ϵ
Answer: A) S ⟶ aA ∣ bBA ⟶ aA ∣ bA′B ⟶ bB ∣ aB′A′ ⟶ aA′ ∣ bCB′ ⟶ bB′ ∣ aCC ⟶ aC ∣ bC ∣ ϵ
These are Theory of Computation Week 4 Nptel Assignment Answers
5. Choose the CFG that generates the same language generated by the regular expression (bab)∗:
A) S ⟶ babS ∣ ϵ B) S ⟶ bS ∣ aS ∣ ϵ C) S ⟶ babS ∣ bab D) S ⟶ baS ∣ abS ∣ ϵ
Answer: A) S ⟶ babS ∣ ϵ
6. Which of the following context-free grammars is ambiguous?
A) S ⟶ 0S1 ∣ ϵ B) S ⟶ 0S1 ∣ 0 ∣ 1 ∣ ϵ C) S ⟶ 0S0 ∣ 1S1 ∣ 0 ∣ 1 ∣ ϵ D) S ⟶ S0 ∣ 0 ∣ 1 ∣ ϵ
Answer: D) S ⟶ S0 ∣ 0 ∣ 1 ∣ ϵ
7. Let D be a DFA with n states that accepts the language L. Let G be the context-free grammar having the least number of non-terminals that generates L. The number of non-terminals in G is at most (select the smallest possible value):
