Theory of Computation
CSE · Quiz · Fall 25
Paper 3 of 3By Md. Ferdous Foysal Hridoy (2)Switch
Paper 3 of 3
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.