Theory of Computation Week 5 Nptel Assignment Answers
Are you looking for Theory of Computation Week 5 Nptel Assignment Answers? You’ve come to the right place! Access the latest and most accurate solutions for your Assignment 5 in the Theory of Computation course. Our detailed answers are designed to help you understand key concepts and excel in your studies.
Course Link: Click Here
Table of Contents
Theory of Computation Week 5 Nptel Assignment Answers (July-Dec 2024)
1. Let (L) be a context-free language. Then according to the pumping lemma for context-free languages, there exists an integer (p \geq 1) such that every string (w \in L) can be written as (w = uvwxy) satisfying the following conditions:
1) (|vx| \geq 1)
2) (|vwx| \leq p)
Which of the following statements is correct?
a) (\forall n \geq 0, u v^n w x^n y \in L)
b) (\exists n \geq 0, u v^n w x^n y \in L)
c) (\forall n \geq 0, u v^n w x^n y^n \in L)
d) (\exists n \geq 0, u v^n w^n x^n y \in L)
Answer: b) (\exists n \geq 0, u v^n w x^n y \in L)
2. Which of the following languages is not context-free?
a) (\emptyset)
b) ({a^m b^n w \mid m, n \geq 0, w \in {0, 1}^* })
c) ({a^n b^n c^m d^m \mid m, n \geq 0})
d) ({w w \mid w \in {0, 1}^* })
Answer: d) ({w w \mid w \in {0, 1}^* })
3. Consider the following PDA.
What is the language accepted by this PDA?
a) Set of all strings of the form (a^n b^n)
b) Set of all strings of the form (b^n a^n)
c) Set of all even-length palindromes over the alphabet ({0, 1})
d) Set of all odd-length palindromes over the alphabet ({0, 1})
Answer: a) Set of all strings of the form (a^n b^n)
4. Consider the following PDA.
Which of the following strings is not accepted by this PDA?
a) 00000000
b) 00000011
c) 00001111
d) 00111111
Answer: c) 00001111
These are Theory of Computation Week 5 Nptel Assignment Answers
5. Which of the following is context-free?
a) ({0^n \mid n \text{ is prime} })
b) ({w w^R \mid w \in {0, 1}^* \text{ and } w^R \text{ is the reverse of } w})
c) ({a^n c^m b^n d^m \mid m, n \geq 0})
d) ({a^n b^n c^n \mid n \geq 0})
Answer: c) ({a^n c^m b^n d^m \mid m, n \geq 0})
These are Theory of Computation Week 5 Nptel Assignment Answers
All Weeks of Theory of Computation: Click here
For answers to additional Nptel courses, please refer to this link: NPTEL Assignment Answers
