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.
Theory of Computation Week 5 Nptel Assignment Answers
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
