Skip to content

Theory of Computation

CSE · Quiz · Fall 25

Paper 3 of 3By Md. Ferdous Foysal Hridoy (2)Switch

Paper 3 of 3

This browser can’t show the PDF here

Open it, and your phone’s PDF viewer takes it, or download it.

Read the questions as text

Read off the PDF by AI, so it may have mistakes. The PDF is the original.

Q1 | a) | Consider the following PDA: P = ({q0, q1, q2, q3, f}, {a, b, c}, {Z0, A, B}, ͅ, q0, Z0, {f}) The language L(P) = { wcw^R | w in {a, b}^+ } Transition functions ͅ are as follows: 1. ͅ(q0, a, Z0) = (q0, AZ0) 2. ͅ(q0, b, Z0) = (q0, BZ0) 3. ͅ(q0, a, A) = (q0, AA) 4. ͅ(q0, b, A) = (q0, BA) 5. ͅ(q0, a, B) = (q0, AB) 6. ͅ(q0, b, B) = (q0, BB) 7. ͅ(q0, c, A) = (q1, A) 8. ͅ(q0, c, B) = (q1, B) 9. ͅ(q1, a, A) = (q1, ̅) 10. ͅ(q1, b, B) = (q1, ̅) 11. ͅ(q1, ̅, Z0) = (f, Z0) Analyze the execution of the PDA and provide the sequence of Instantaneous Descriptions (IDs) to demonstrate that the strings: - "aba c aba" b) | Using the Pumping Lemma, prove that the language L = {a^n b^n c^n | n >= 1} is not regular.