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 (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

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